poj 1036 Gangsters

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;
}
这个程序应该能优化时间复杂度的，以前做过一个。以后可能有补充。

补充：软件开发 , C++ ,