#include <iostream>
#define MAXN 100
#define MAXK 100
#define MAXT 30000
#define MAX 100000
using namespace std;

struct Gangster {
	int t,p,s;
};
int n,k,t;
Gangster g[100];
int price[MAXK+1][MAXT+1],dp[MAXK+1][MAXT+1];

void input();
void DP();
int max(int a,int b,int c=-MAX);

int main()
{
	int i,best;
	input();
	memset(price,0,sizeof(price));
	for (i=0;i<n;i++)  price[g[i].s][g[i].t]=g[i].p;
	DP();
	best=0;
	for (i=0;i<=k;i++)
		if (dp[i][t]>best)  best=dp[i][t];
	cout<<best<<endl;
	return 0;
}

void input()
{
	
	int i;
	cin>>n>>k>>t;
	for (i=0;i<n;i++)  cin>>g[i].t;
	for (i=0;i<n;i++)  cin>>g[i].p;
    for (i=0;i<n;i++)  cin>>g[i].s;
}
void DP()
{
	int i,j;
	dp[0][0]=0;
	for (i=1;i<=k;i++)  dp[i][0]=-MAX;	
	for (j=1;j<=t;j++)
	{
		for (i=0;i<=k;i++)
		{
			if (i==0)  dp[i][j]=max(dp[i][j-1],dp[i+1][j-1])+price[i][j];
			else if (i==k) dp[i][j]=max(dp[i][j-1],dp[i-1][j-1])+price[i][j];
			else dp[i][j]=max(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1])+price[i][j];
		}
	}
}
int max(int a,int b,int c)
{
	int temp=(a>b?a:b);
	return (temp>c?temp:c);
}

• Re:请教一下，我的这个程序为什么会超内存呢？ (1244) newton 2006-02-14 11:23:10
• Re:请教一下，我的这个程序为什么会超内存呢？ (1244) 070220219 2009-11-08 10:47:35
  • Re:请教一下，我的这个程序为什么会超内存呢？ (71) 070220219 2009-11-08 10:49:44