uva 10891 

题目大意:两个人轮流从数组里面取数，可以在头或者尾选择连续的任意多个，直到取完。最后统计两个人取走的数之和，两个人都尽量让自己的得分高，求A的得分减去B的得分。

分析：这题的关键是只能在头尾取，把数组看成一个序列（i~j），那么取走k个数后仍是一个连续的序列（i+k,j）或（i,j-k）。

我们用dp[i][j]表示碰到（i，j）这个序列能得到的最高分数。

那么我们考虑如何转移，这里有点博弈的思想，我们要现在这个状态最高即要求对方碰到的状态（即自己取完后的状态）的得分越少越好。

那么状态转移方程就是dp[i][j]=sum[i][j]-min{dp[i+1][j]....dp[j][j],dp[i][j-1]....dp[i][i],0}。

 

1 /*dp[i][j]=sum[i][j]-min{dp[i+1][j]....dp[j][j],dp[i][j-1]....dp[i][i],0} 2  *   3 */ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #define maxlen 110 8 using namespace std; 9 int dp[maxlen][maxlen];10 int sum[maxlen];//the sum of 0~i11 bool used[maxlen][maxlen];12 int min(int a,int b)13 {14     return a
         
          =i;--k)25         ans=min(ans,dfs(i,k));26     return dp[i][j]=sum[j]-sum[i-1]-ans;27 }28 int main ()29 {30     int n;31     while(scanf("%d",&n)!=EOF)32     {33         if(n==0)34             break;35         sum[0]=0;36         for(int i=1;i<=n;++i)37         {38             int x;39             scanf("%d",&x);40             sum[i]=sum[i-1]+x;41         }42         memset(used,false,sizeof(used));43         int ans=2*dfs(1,n)-sum[n];44         printf("%d\n",ans);45     }    46 }
         
        
       
      

 uva 11584 

题目大意：给你一个字符串，把它划分为回文串，问最小的回文串个数

分析：dp[i]表示字符串(1,i)的最小回文串个数

状态转移就是枚举子集，求一个最小值

方程为：dp[i]=min{dp[j-1]+1,dp},j<=i&&字符串（j，i）为回文串

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #define maxlen 1010 6 #define INF 0x3fffff 7 using namespace std; 8 int dp[maxlen]; 9 char str[maxlen];10 int min(int a,int b)11 {12     return a
         
        
       
      

 uva 10405 

题目大意:最经典的LCS问题，最长公共子序列。

dp[i][j]表示str匹配到i,str2匹配到j时的最大长度。

状态转移方程为：

d[i][j]=dp[i-1][j-1]+1 (str[i]==str2[j])

dp[i][j]=max(dp[i-1][j],dp[i][j-1])(str[i]!=str2[j])

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define maxlen 1010 5 using namespace std; 6 int dp[maxlen][maxlen]; 7 char str[maxlen]; 8 char str2[maxlen]; 9 int main ()10 {11     while(gets(str))12     {13         gets(str2);14         int len=strlen(str);15         int len2=strlen(str2);16         memset(dp,0,sizeof(dp));17         for(int i=1;i<=len;++i)18         {19             for(int j=1;j<=len2;++j)20             {21                 if(str[i-1]==str2[j-1])22                     dp[i][j]=dp[i-1][j-1]+1;23                 else 24                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);25             }26         }27         printf("%d\n",dp[len][len2]);28     } 29 }
        
       
      

 uva 674 

题目大意:有50,25,10,5,1五种硬币，现在给你n问有多少种兑换方式

分析:

dp[i]表示兑换种数

状态方程就是dp[i]=sum{dp[i-num[j]]}(0<=j<5&&i>=num[j])

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define maxlen 7500 5 using namespace std; 6 int dp[maxlen]; 7 int num[]={
    50,25,10,5,1}; 8 int main () 9 {10     int n;11     dp[0]=1;12     for(int i=0;i<5;++i)13     {14         for(int j=0;j
         
          =num[i])17                 dp[j]+=dp[j-num[i]];18         }19     }20     while(scanf("%d",&n)!=EOF)21     {  22         printf("%d\n",dp[n]);23     }24 }
         
        
       
      

 uva 10003 

题目大意：给你长度n的木棍，以及m个要切割的位置。问如何安排顺序是的花费最小，花费的定义是每次切割时木棍的长度之和。

分析：本题最主要的是状态的划分，一开始不知道如何下手，本来想从起始两端的位置dp，后来发现没用。

后来想到用切割的位置来dp

dp[i][j]表示在已有的切割要求下完成切割所需要的最小代价，区间i, j表示第i个和第j个切割点，初始为0，结束为最后一个节点，之间为输入切割点数

切割点的位置是一定的，但是切割的时候剩余的木块长度不一定，所以有

dp[i,j] = min{ dp[i, k] + dp[k, j] } + num[j] - num[i]    (i<k<j) 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define maxlen 60 5 #define INF 0x3fffff 6 using namespace std; 7 int dp[maxlen][maxlen]; 8 int num[maxlen]; 9 int dfs(int i,int j)10 {11     if(i==j-1)12         return dp[i][j]=0;13     if(dp[i][j]!=-1)14         return dp[i][j];15     dp[i][j]=INF;16     for(int k=i+1;k
        
       
      

 uva 116 

题目大意：给以n*m矩阵，要求求从0列到m-1列的一条路径使得和最小，在行上面是循环的即最后一行向下走一步就回到第一行

方向有三个：

 要求输出字典序最小的路径以及最小值

分析：dp[i][j]表示走到(i,j)位置的最小值，那么它是由三个状态dp[(i-1)%n][j+1],dp[i][j+1],dp[(i+1)%n][j]转化过来的,三者取一下最小值然后记录路径即可。

方程为：dp[i][j]=min{dp[(i-1)%n][j+1],dp[i][j+1],dp[(i+1)%n][j]}+map[i][j]

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define maxlen 210 5 #define INF 0x3ffffff 6 #define min(a,b)(a
         
          =0;--j)26         {27             for(int i=0;i
          
           dp[i][0])45             {46                 c=i;47                 ans=dp[i][0];48             }49         }50         printf("%d",c+1);51         c=path[c][0]; 52         for(int j=1;j
          
         
        
       
      

 uva 10066 

题目大意：最长公共子序列

方程见上面的，是差不多的（一样的）。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define maxlen 110 5 #define INF 0x3ffffff 6 #define max(a,b)(a>b?a:b) 7 using namespace std; 8 int dp[maxlen][maxlen]; 9 int num[maxlen];10 int num2[maxlen];11 int n,m;12 int main ()13 {14     int Case=1;15     while(scanf("%d%d",&n,&m)!=EOF)16     {17         if(n==0&&m==0)18             break;19         for(int i=1;i<=n;++i)20             scanf("%d",&num[i]);21         for(int i=1;i<=m;++i)22             scanf("%d",&num2[i]);23         memset(dp,0,sizeof(dp));24         for(int i=1;i<=n;++i)25         {26             for(int j=1;j<=m;++j)27             {28                 if(num[i]==num2[j])29                     dp[i][j]=dp[i-1][j-1]+1;30                 else 31                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);32             }33         }34         printf("Twin Towers #%d\n",Case++);35         printf("Number of Tiles : %d\n\n",dp[n][m]);36     }37 }
        
       
      

 uva 357 

跟上面的钱币兑换是一样的，注意要用longlong 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define maxlen 30010 5 using namespace std; 6 long long  dp[maxlen]; 7 int num[]={
    50,25,10,5,1}; 8 int main () 9 {10     int n;11     dp[0]=1;12     for(int i=0;i<5;++i)13     {14         for(int j=0;j
         
          =num[i])17                 dp[j]+=dp[j-num[i]];18         }19     }20     while(scanf("%d",&n)!=EOF)21     {22         if(dp[n]==1)23             printf("There is only 1 way to produce %d cents change.\n",n);24         else  25             printf("There are %lld ways to produce %d cents change.\n",dp[n],n); 26     }27 }
         
        
       
      

 uva 562 

题目大意：把一些钱num[]分给两个人，要求尽量使两个人得到的钱只差最小，输出最小的差值、

分析：我们这么考虑这个问题，num[i]只能分给一个人，0表示分给第一个人，1表示分给第二个人，那么可以从0-1背包方向考虑。

假设总钱数为sum且A分得的钱不超过B，dp[i]表示A是否可以分得一些硬币使得其总钱数为i，dp[i]为1表示可以，0表示不可以。

那么就是0-1背包问题的变形了

dp[0]=1。然后分别对每个硬币枚举，判断dp是否为1即可。最后选择离Sum/2最近且dp[i]==1的i即可。

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #define maxlen 50010 5 using namespace std; 6 bool dp[maxlen]; 7 int num[110]; 8 int n; 9 int main()10 {11     int t;12     scanf("%d",&t);13     while(t--)14     {15         scanf("%d",&n);16         int sum=0;17         for(int i=0;i
          
           =num[i];--j)27             {28                 if(!dp[j])29                     dp[j]=dp[j-num[i]];30             }31         }32         for(int i=sum/2;i>=0;--i)33         {34             if(dp[i])35             {36                 printf("%d\n",sum-i-i);37                 break;38             }39         }40     }41 }
          
         
        
       

 uva 10130 

题目大意：每种物品有价值与重量，现在有n个人，给出每个人能承受的最大重量，问这些人最多能够拿到的物品最大值是多少。

分析:多人的0-1背包，只是对每个人用0-1背包求最大值然后加起来就可以了。

使用滚动数组可以把二维的优化到一维。dp[i]表示容量i能装下的最大价值

状态转移方程维：

dp[i]=max{dp[i],dp[i-w]+v} if (i>=w)

dp[i]=dp[i] (i<w)初始化为0

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #define maxlen 1010 5 using namespace std; 6 int w[maxlen],v[maxlen],dp[maxlen]; 7 int n,g; 8 int main () 9 {10     int t;11     scanf("%d",&t);12     while(t--)13     {14         scanf("%d",&n);15         memset(dp,0,sizeof(dp));16         for(int i=1;i<=n;++i)17         {18             scanf("%d%d",&v[i],&w[i]);19             for(int j=30;j>=0;--j)20             {21                 if(j>=w[i])22                     dp[j]=max(dp[j],dp[j-w[i]]+v[i]);23             }24         }25         scanf("%d",&g);26         int ans=0;27         int x;28         for(int i=0;i
         
        
       

 uva 624 

分析：0-1背包，可以理解为价值与重量是一样的0-1背包，需要记录路径。

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #define maxlen 2010 5 using namespace std; 6 int v[30],dp[maxlen]; 7 bool path[30][maxlen]; 8 int V,n; 9 int main ()10 {11     while(scanf("%d%d",&V,&n)!=EOF)12     {13         for(int i=1;i<=n;++i)14             scanf("%d",&v[i]);15         memset(dp,0,sizeof(dp));16         memset(path,0,sizeof(path));17         for(int i=n;i>=1;--i)18         {19             for(int j=V;j>=v[i];--j)20             {21                 if(j>=v[i]&&dp[j]
         
        
       

 uva 147 

分析：跟上面的钱币兑换类似，这里有个优化的就是题目说的是5的倍数，那么每个都除以5，会使程序速度更快。

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #define maxlen 20010 5 using namespace std; 6 long long  dp[maxlen]; 7 int cc[]={
     1,2,4,10,20,40,100,200,400,1000,2000}; 8 int n; 9 int main()10 {11     int i,j,k;12     double num;13     while (scanf("%lf",&num),num>0) 14     {15         n=int((num+0.005)*100);16         n/=5;17         memset(dp,0,sizeof(dp));18         dp[0]=1;19         for (int i=0;i<=10;++i) 20         {21             for (int j=0;j<=n;++j)22             {23                 if(j>=cc[i])24                     dp[j]+=dp[j-cc[i]];               25             }26         }27         printf("%6.2lf%17lld\n",num,dp[n]);28     }29 }