poj 1036 Gangsters 简单dp

//poj 1036
//sep9
//这种dp效率低 会爆内存
#include <iostream>
using namespace std;
const int MAXT=30012;
const int MAXS=112;
const int MAXN=112;
int n,k,t;
int a[MAXT][MAXS];
int dp[MAXT][MAXS];
int x[MAXN],y[MAXN],z[MAXN];
int main()
{scanf("%d%d%d",&n,&k,&t);int maxT=0,maxS=0;for(int i=0;i<n;++i){scanf("%d",&x[i]);maxT=max(maxT,x[i]);}for(int i=0;i<n;++i)scanf("%d",&y[i]);	for(int i=0;i<n;++i){scanf("%d",&z[i]);maxS=max(maxS,z[i]);}memset(a,0,sizeof(a));memset(dp,-1,sizeof(dp));for(int i=0;i<n;++i)a[x[i]][z[i]]+=y[i];dp[0][0]=a[0][0];for(int time=1;time<=maxT;++time)for(int sta=0;sta<=MAXS;++sta){if(sta-1>=0&&dp[time-1][sta-1]!=-1)dp[time][sta]=max(dp[time][sta],dp[time-1][sta-1]+a[time][sta]);if(dp[time-1][sta]!=-1)dp[time][sta]=max(dp[time][sta],dp[time-1][sta]+a[time][sta]);	if(dp[time-1][sta+1]!=-1)dp[time][sta]=max(dp[time][sta],dp[time-1][sta]+a[time][sta]);}int ans=-1;for(int i=0;i<=MAXS;++i)ans=max(ans,dp[maxT][i]);if(ans==-1)printf("0");elseprintf("%d",ans);		return 0;	
} //改变思考问题角度后的新dp AC
#include <iostream>
#include <algorithm>
using namespace std;struct Node
{int t,s,v;	
}g[128];int n,k,t;
int dp[128];int cmp(Node x,Node y)
{return x.t<y.t;
}int main()
{scanf("%d%d%d",&n,&k,&t);for(int i=1;i<=n;++i)scanf("%d",&g[i].t);for(int i=1;i<=n;++i)scanf("%d",&g[i].v);for(int i=1;i<=n;++i)scanf("%d",&g[i].s);	int ans=-1;memset(dp,-1,sizeof(dp));dp[0]=0;g[0].t=0,g[0].s=0,g[0].v=0;sort(g+1,g+1+n,cmp);for(int i=1;i<=n;++i){for(int j=0;j<i;++j){if(dp[j]!=-1&&abs(g[i].s-g[j].s)<=g[i].t-g[j].t)dp[i]=max(dp[i],dp[j]+g[i].v);}ans=max(ans,dp[i]);}printf("%d",ans==-1?0:ans);return 0;	
}