[CodeVS 1154]能量项链

danihao123 posted @ 2016年9月16日 16:00 in 题解 with tags CodeVS 动态规划 环状DP , 184 阅读
转载请注明出处:http://danihao123.is-programmer.com/

环状DP填坑辣……

这个就是把矩阵连乘出到了环上。很容易想到的方法是枚举断点断环成链,当成简单的矩阵连乘做,不过这样的时间复杂度为[tex]O(n^4)[/tex],有点慢。我们可以直接把序列复制一份放到原序列后面,然后当成矩阵连乘做,这样的话时间复杂度仅为[tex]O(n^3)[/tex],挺优秀的。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=205;
long long d[maxn][maxn];
long long e[maxn];
int main(){
    register int i,j,k;
    register long long temp,ans=0;
    int n;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&e[i]);
        e[i+n]=e[i];
    }
    for(j=2;j<2*n;j++)
        for(i=j-1;i>=1 && (j-i+1)<=n;i--){
            for(k=i;k<j;k++){
                temp=d[i][k]+d[k+1][j]+e[i]*e[k+1]*e[j+1];
                d[i][j]=max(d[i][j],temp);
            }
            ans=max(ans,d[i][j]);
        }
    printf("%lld\n",ans);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter