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 ans;
void dfs(int p,int max)
{
if(max>ans) ans=max;
int i;
for(i=2;i<=n;i++)
{
if(map[p][i])
{
max++;
dfs(i,max);
max--;
}
}
}
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;
}
ans=0;
dfs(1,0);
printf("%d\n",ans);
}
return 0;
}
F题：经典的入门题，大家都会了，就跳过
G
http://poj.org/problem id=2385
总共有两棵苹果树，时不时的会掉下苹果来，你最多只能往返两棵苹果树W次，给你第i分钟在哪颗苹果树会掉苹果的信息，问你最多能拿到多少的苹果
题目给出一个时间，一个次数两个限制，那么我们描述状态的时候就应该把它们描述进去
dp[i][j]代表前i分钟，最多（注意是最多）已经往返了j次的时候收获到的最多的苹果的数量，那么状态转移就很简单了，利用j的奇偶性我们可以判断出当前在那棵苹果树
记住！！！每次都有两种决策，要么停留在当前苹果树，要么离开当前苹果树
dp[i][j]=max(dp[i][j],dp[i-1][j]+(j%2+1==num[i]));
//停留在i-1时刻的苹果树
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(j%2==num[i]))
//换一棵苹果树
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(j%2+1==num[i]));
//也可以不换苹果树
[cpp]
#include
#include
int dp[1010][35];
int num[1010];
int max(int a,int b){
return a>b a:b;
}
int main(){
int T,W,i,j;
while(scanf("%d%d",&T,&W)!=EOF){
for(i=1;i<=T;i++) scanf("%d",&num[i]);
memset(dp,0,sizeof(dp));
if(num[1]==1) dp[1][0]=1;
dp[1][1]=1;
for(i=2;i<=T;i++){
for(j=0;j<=W;j++){
if(j==0) {
dp[i][j]=dp[i-1][j]+num[i]%2;
continue;
}
dp[i][j]=max(dp[i][j],dp[i-1][j]+(j%2+1==num[i]));
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(j%2==num[i]));
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(j%2+1==num[i]));
}
}
printf("%d\n",dp[T][W]);
}
}
H
http://poj.org/problem id=1976
dp[i][j]表示前i节车厢用j个火车头去拉所能拉的最大乘客量
转移过程很简单，尝试着自己推一下，具体见代码，看看能不能看懂是怎么转移的
[cpp]
#include
#include
int dp[55555][4],a[55555];
int max(int a,int b)
{
return a>b a:b;
}
int main()
{
int t,i,j,k,n,m;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
a[0]=0;
for(i=1;i<=n;i++) scanf("%d",&a[i]),a[i]+=a[i-1];
scanf("%d",&m);
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(j=1;j<4;j++)
{
k=i-m;
if(k<0) k=0;
dp[i][j]=max(dp[i-1][j],dp[k][j-1]+a[i]-a[k]);
}
printf("%d\n",dp[n][3]);
}
return 0;
}
I,J 两题都是一类最简单的树形DP，依赖关系形成了一棵树，选择父节点就一定不能选择子节点
DP过程
注意：对于每个矛盾关系，从老板向员工连一条边
dp[i][0]表示不取i的最大值，可以由两个状态转移而来dp[i][0]+=sigma[max（dp[j][0],dp[j][1]）],j为儿子，即儿子取或不取都可以
dp[i][1]表示取i的最大值，初