uva 10891 game of sum

题目链接

详细请参考刘汝佳《算法竞赛入门经典训练指南》 p67

  

   

    

     

    
    

     

      //2013-05-01-20.40
     
    
   

    

     

    
    

     

      //uva 10891
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      const int maxn = 105;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool vis[maxn][maxn];
     
    
   

    

     

    
    

     

      int s[maxn];
     
    
   

    

     

    
    

     

      int d[maxn][maxn];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int dp(int i, int j)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    if (vis[i][j])
     
    
   

    

     

    
    

     
        return d[i][j];
     
    
   

    

     

    
    

     

          vis[i][j] = true;
     
    
   

    

     

    
    

     
    int m = 0;
     
    
   

    

     

    
    

     
    for (int k = i+1; k <= j; k++)
     
    
   

    

     

    
    

     

              m = min(dp(k,j), m);
     
    
   

    

     

    
    

     
    for (int k = i; k < j; k++)
     
    
   

    

     

    
    

     

              m = min(dp(i, k), m);
     
    
   

    

     

    
    

     

          d[i][j] = s[j] - s[i-1] - m;
     
    
   

    

     

    
    

     
    return d[i][j];
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int n;
     
    
   

    

     

    
    

     
    while (scanf("%d", &n) && n)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        int a;
     
    
   

    

     

    
    

     

              s[0] = 0;
     
    
   

    

     

    
    

     
        for (int i = 1; i <= n; i++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            scanf("%d" ,&a);
     
    
   

    

     

    
    

     

                  s[i] = s[i-1] + a;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        memset(vis, false, sizeof(vis));
     
    
   

    

     

    
    

     
        printf("%d\n", 2*dp(1, n) - s[n]);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/8981785