【滚动数组】 dp poj 1036

题意：一群匪徒要进入一个酒店。酒店的门有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=102,K=102,T=30002;
int dp[2][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=1;i<=n;i++)
    flag[gan[i].t]=true;
    int w;
    sort(gan+1,gan+n+1,cmp);
    for(int i=1;i<=t;i++)
    {
        for(int j=0;j<=k && j<=i;j++)
        {
            w=0;
            if(flag[i])
            {
                for(int ii=1;ii<=n;ii++)
                {
                    if(gan[ii].t==i && gan[ii].s==j)
                    w+=gan[ii].p;
                }
            }
            if(j==k)
    dp[i%2][j]=max(dp[(i-1)%2][j-1],dp[(i-1)%2][j]);
   else if(j==0)
    dp[i%2][j]=max(dp[(i-1)%2][j+1],dp[(i-1)%2][j]);
   else
    dp[i%2][j]=max(dp[(i-1)%2][j-1],max(dp[(i-1)%2][j+1],dp[(i-1)%2][j]));
   dp[i%2][j]+=w;
        }
    }
    int ans=0;
    for(int j=0;j<=k;j++)
    {
        ans=max(ans,dp[t%2][j]);
    }
    cout << ans << endl;
}
int main()
{
 freopen("in.txt","r",stdin);
 scanf("%d%d%d",&n,&k,&t);
 for(int j=1;j<=n;j++)
 {
  scanf("%d",&gan[j].t);
 }
 for(int j=1;j<=n;j++)
 {
  scanf("%d",&gan[j].p);
 }
 for(int j=1;j<=n;j++)
 {
  scanf("%d",&gan[j].s);
 }
 solve();
 return 0;
}