HDU 3506 DP 四边形不等式优化 Monkey Party

攻城狮东宸技术 2022年11月7日

0 收藏 485 点赞 567 浏览 698 个字

环形石子合并问题。

有一种方法是取模，而如果空间允许的话(或者滚动数组)，可以把长度为n个换拓展成长为2n-1的直线。

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <algorithm> using namespace std; const int maxn =  + ;
 const int INF = 0x3f3f3f3f; int n; int a[maxn], sum[maxn];
 int d[maxn][maxn], s[maxn][maxn]; int main()
 {
     while(scanf("%d", &n) ==  && n)
     {
         for(int i = ; i <= n; i++) scanf("%d", a + i);
         for(int i = n + ; i < n * ; i++) a[i] = a[i - n];
         for(int i = ; i < n * ; i++) sum[i] = sum[i - ] + a[i];         for(int i = ; i +  < n * ; i++)
         {
             s[i][i+] = i;
             d[i][i+] = a[i] + a[i+];
         }         for(int l = ; l <= n; l++)
         {
             for(int i = ; i + l -  < n * ; i++)
             {
                 int j = i + l - ;
                 d[i][j] = INF;
                 for(int k = s[i][j-]; k <= s[i+][j]; k++)
                 {
                     int t = d[i][k] + d[k+][j] + sum[j] - sum[i-];
                     if(t < d[i][j])
                     {
                         d[i][j] = t;
                         s[i][j] = k;
                     }
                 }
             }
         }         int ans = INF;
         for(int i = ; i <= n; i++) ans = min(ans, d[i][i+n-]);
         printf("%d\n", ans);
     }     return ;
 }