题意：一群匪徒要进入一个酒店。酒店的门有k+1个状态，每个匪徒的参数是：进入时间，符合的状态，携带的钱。
酒店的门刚开始状态0，问最多这个酒店能得到的钱数。
思路：
dp数组为DP[T][K].
转移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1])
因为转移i只跟i-1有关，所以可以用滚动数组dp[2][k].
其实这道题的转移方程很容易想到，只是编程的时候处理边界等细节比较麻烦。还有学习了滚动数组
#include <iostream>
#include <cstdio>
#include <algorithm> using namespace std;
const int N=,K=,T=;
int dp[][K];
struct gang
{
int t,p,s;
}gan[N]; bool cmp(const gang &a,const gang &b)
{
return a.t < b.t;
}
int n,k,t;
bool flag[T];
void solve()
{
for(int i=;i<=n;i++)
flag[gan[i].t]=true;
int w;
sort(gan+,gan+n+,cmp);
for(int i=;i<=t;i++)
{
for(int j=;j<=k && j<=i;j++)
{
w=;
if(flag[i])
{
for(int ii=;ii<=n;ii++)
{
if(gan[ii].t==i && gan[ii].s==j)
w+=gan[ii].p;
}
}
if(j==k)
dp[i%][j]=max(dp[(i-)%][j-],dp[(i-)%][j]);
else if(j==)
dp[i%][j]=max(dp[(i-)%][j+],dp[(i-)%][j]);
else
dp[i%][j]=max(dp[(i-)%][j-],max(dp[(i-)%][j+],dp[(i-)%][j]));
dp[i%][j]+=w;
}
}
int ans=;
for(int j=;j<=k;j++)
{
ans=max(ans,dp[t%][j]);
}
cout << ans << endl;
}
int main()
{
freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&k,&t);
for(int j=;j<=n;j++)
{
scanf("%d",&gan[j].t);
}
for(int j=;j<=n;j++)
{
scanf("%d",&gan[j].p);
}
for(int j=;j<=n;j++)
{
scanf("%d",&gan[j].s);
}
solve();
return ;
}