POJ的第2個題。也是動歸，其中dp[i][j]表示是第i個時刻，門開到j的程度時的最大價值。
當然了狀態比較好想的，此時刻的價值必然與前面的時刻是有關的，聯系就是前一個時刻的j，也就是與前一時刻的門的程度是相關的，並且一個時刻門只有三種可能。1：開一個單位。2：關一個單位。3：與之前的一樣。並且要使用滾動數組來做這個，不然我的內存可能會超，沒試過因為這種動態轉移方程一般都用滾動數組來節省空間，直接看會就是一勞永逸的事了。下面附代碼。
[cpp]
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int time;
int value;
int silm;
};
node gangster[110];
int mark[30010];
int dp[3][110];
bool cmp(node a,node b)
{
if(a.time<b.time)
return true;
else return false;
}
int maxi(int a,int b)
{
if(a>b)
return a;
else return b;
}
int main()
{
int N,K,T,i,j,w,p,mabi;
cin>>N>>K>>T;
for(i=1;i<=N;i++)
{
cin>>gangster[i].time;
mark[gangster[i].time]=1;
}
for(i=1;i<=N;i++)
cin>>gangster[i].value;
for(i=1;i<=N;i++)
cin>>gangster[i].silm;
sort(gangster+1,gangster+1+N,cmp);
mabi=0;
for(i=0;i<=T;i++)
for(j=0;j<=i&&j<=K;j++)
{
w=0;
dp[i%2][j]=0;
if(mark[i]==1)
{
for(p=1;p<=N;p++)
{
if(gangster[p].time==i&&gangster[p].silm==j)
w=w+gangster[p].value;
}
}
if(j==0)
{
dp[i%2][j]=maxi(dp[1-i%2][j],dp[1-i%2][j+1]);
}
else if(j==K)
{
dp[i%2][j]=maxi(dp[1-i%2][j],dp[1-i%2][j-1]);
}
else dp[i%2][j]=maxi(maxi(dp[1-i%2][j],dp[1-i%2][j-1]),dp[1-i%2][j+1]);
dp[i%2][j]+=w;
if(dp[i%2][j]>mabi)
mabi=dp[i%2][j];
}
cout<<mabi<<endl;
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int time;
int value;
int silm;
};
node gangster[110];
int mark[30010];
int dp[3][110];
bool cmp(node a,node b)
{
if(a.time<b.time)
return true;
else return false;
}
int maxi(int a,int b)
{
if(a>b)
return a;
else return b;
}
int main()
{
int N,K,T,i,j,w,p,mabi;
cin>>N>>K>>T;
for(i=1;i<=N;i++)
{
cin>>gangster[i].time;
mark[gangster[i].time]=1;
}
for(i=1;i<=N;i++)
cin>>gangster[i].value;
for(i=1;i<=N;i++)
cin>>gangster[i].silm;
sort(gangster+1,gangster+1+N,cmp);
mabi=0;
for(i=0;i<=T;i++)
for(j=0;j<=i&&j<=K;j++)
{
w=0;
dp[i%2][j]=0;
if(mark[i]==1)
{
for(p=1;p<=N;p++)
{
if(gangster[p].time==i&&gangster[p].silm==j)
w=w+gangster[p].value;
}
}
if(j==0)
{
dp[i%2][j]=maxi(dp[1-i%2][j],dp[1-i%2][j+1]);
}
else if(j==K)
{
dp[i%2][j]=maxi(dp[1-i%2][j],dp[1-i%2][j-1]);
}
else dp[i%2][j]=maxi(maxi(dp[1-i%2][j],dp[1-i%2][j-1]),dp[1-i%2][j+1]);
dp[i%2][j]+=w;
if(dp[i%2][j]>mabi)
mabi=dp[i%2][j];
}
cout<<mabi<<endl;
return 0;
}
這個程序應該能優化時間復雜度的，以前做過一個。以後可能有補充。
