动态规划训练第一阶段（for初学者）(二)

D题
http://poj.org/problem id=2537

Dp[i][j]代表前i个数最后一个是j时，总共的tights的数量，以为前后两个字符串的绝对值差不能超过1，那么转移过程显而易见
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1];
在这个方程里[i-1]这一维的数都是已经求好的最优子结构
[cpp]
#include
#include
double dp[110][15];
int main()
{
int k,n;
int i,j;
while(scanf("%d%d",&k,&n)!=EOF)
{
memset(dp,0,sizeof(dp));
for(i=1;i<=k+1;i++)
dp[1][i]=1;
for(i=2;i<=n;i++)
for(j=1;j<=k+1;j++)
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1];
double ans=0;
for(i=1;i<=k+1;i++)
ans+=dp[n][i];
for(i=1;i<=n;i++)
ans/=(k+1);
ans*=100;
printf("%.5lf\n",ans);
}
return 0;
}

E:
http://poj.org/problem id=3018
DAG上最长路
给出很多个盒子的大小，将小的盒子放入大的盒子，再将大的盒子放入更大的盒子，如此下去问你最多能有多少个盒子嵌套在一起

典型的DAG上最长路问题
DAG(DirectedAcyclic Graph)有向无环图，因为一个盒子能放进另一个盒子，另一个盒子肯定就放不进这个盒子，所以关系是单向的，也就是说形成的图是有向的，而且肯定不会有环。
状态
dp[i]表示到达i这个点所经过的最长路，那么可以用这个状态尝试着去更新i可以到达的点j
dp[j]=max(dp[j],dp[i]+1);
最后的答案就是dp[i]的最大值

还有一种写法是dfs搜一条最长路，具体见代码
[cpp]
#include
#include
#include
using namespace std;
const int inf = 100000000;
int box[510][1010];
int map[510][510];
int n,d;
bool ok;
int count=0;
bool solve(int a,int b)
{
int i,j;
bool flag=true;
for(i=1;i<=d;i++)
{
if(box[a][i]>=box[b][i])
{
flag=false;
break;
}
}
return flag;
}
void init()
{
int i,j;
memset(map,0,sizeof(map));
for(i=2;i<=n;i++)
{
if(solve(1,i))
{
map[1][i]=1;
ok=true;
}
}
for(i=2;i<=n;i++)
{
for(j=2;j<=n;j++)
{
if(solve(i,j))
{
map[i][j]=1;
}
}
}
}
int dp[510];
int main()
{
int i,j,k;
while(scanf("%d%d",&n,&d)!=EOF)
{
n++;
ok=false;
for(i=1;i<=n;i++)
{
for(j=1;j<=d;j++)
{
scanf("%d",&box[i][j]);

}sort(box[i]+1,box[i]+1+d);
}
init();
if(!ok)
{
printf("Please look for another gift shop!");
continue;
}
dp[1]=0;
for(i=2;i<=n;i++)
dp[i]=-1;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(map[i][j]&&dp[i]!=-1)
{
if(dp[i]+1>dp[j])
{
dp[j]=dp[i]+1;
}
}
}
}
int ans=0;
for(i=1;i<=n;i++)
{
if(dp[i]>ans)
ans=dp[i];
}
printf("%d\n",ans);
}
return 0;
}

[cpp]
#include
#include
#include
using namespace std;
const int inf = 100000000;
int box[510][1010];
int map[510][510];
int n,d;
bool ok;
int count=0;
bool solve(int a,int b)
{
int i,j;
bool flag=true;