http://acm.hdu.edu.cn/showproblem.php?pid=1684

这是一个二维的DP简单题   最近在做DP专题   呵呵   还是第一次做到二维的呢   爽

A题不多  只求在比赛前能多熟悉下DP的各种类型。。。。。

#include<stdio.h>
#include<string.h>
int p[101][101];
int dp[101][101];
int a[101];
int reward[101];
int punishment[101];
int main()
{
 int m,n,t,max,i,j,k,salary,w;
 scanf("%d",&t);
 while(t--)
 {
  memset(p,0,sizeof(p));
  scanf("%d",&m);
  scanf("%d",&n);
  scanf("%d",&salary);
  for(i=0;i<m;i++)
  {
   for(j=1;j<=n;j++)
    scanf("%d",&p[i][j]);
   scanf("%d%d",&reward[i],&punishment[i]);
  }
  for(i=0;i<=m;i++)
   for(j=0;j<=n;j++)
    dp[i][j]=-2000000000;
  dp[0][0]=0;
  for(i=0;i<m;i++)
  {
   for(j=0;j<=n;j++)
   {
    for(k=0;k<=j;k++)
     if(dp[i][k]!=-2000000000)
    {
     w=(reward[i] - salary * (j-k) )*p[i][j-k] - punishment[i] * (100 - p[i][j-k]);
     if(dp[i+1][j] < dp[i][k] + w)
      dp[i+1][j]=dp[i][k] + w;
    }
   }
  }
  max=-2000000000;k=0;
  for(i=0;i<=n;i++)
   if(max<dp[m][i])
    max=dp[m][i];
  printf("%d\n",max);
  for(i=0;i<=n;i++)
   if(max==dp[m][i])
    a[k++]=i;
  for(i=0;i<k-1;i++)
   printf("%d ",a[i]);
  printf("%d\n",a[k-1]);
 }
 return 0;
}