题解

159 条题解

  • 6
    @ 2016-03-27 22:32:54

    要说的都在程序里:
    ```c++
    #include<iostream>
    using namespace std;

    int n,head[201],tail[201],f[201][201];
    //f[i][j]为起始为i终点为j的链融合生成的最大能量
    //head和tail要拓展数组不然越界要考虑模
    //珠子 1 2 3 4 5(1) 6(2) 7(3)
    //head 1 3 5 7 1 3 5
    //tail 3 5 7 1 3 5 7
    //没有再考虑4是因为不需要,枚举不到

    void read()
    {
    int i,j,k,len,max1;

    cin>>n;
    cin>>head[1];
    for(i=2; i<=n; i++)
    {
    cin>>head[i];

    tail[i-1]=head[i];
    }
    tail[n]=head[1];//读入

    for(i=n+1; i<=2*n-1; i++)
    {
    head[i]=head[i-n];
    tail[i]=tail[i-n];
    }//拓展数组

    for(len=1; len<=n; len++)//枚举链长
    for(i=1; i<=2*n-1-len; i++)//枚举起始位置
    {
    j=i+len;//结束位置

    for(k=i; k<j; k++)//寻找在中间某一位置断开,把两边合并
    f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);
    //从i到j的最大能量=max(当前能量,从i到k的最大能量+从k+1到j的最大能量
    //+两颗珠子合并释放的能量)
    //注意我们把i到k,k+1到j看做两颗已经合并的珠子,只需把这两颗合并
    }

    max1=0;
    for(i=1; i<=n; i++)
    if(f[i][n+i-1]>max1)
    max1=f[i][n+i-1];//枚举起始点找最大

    cout<<max1<<endl;

    return;
    }

    int main()
    {
    read();
    return 0;
    }
    ```

    • @ 2016-11-16 13:28:30

      好评

    • @ 2017-11-06 20:06:00

      讲的很清楚

    • @ 2017-12-01 20:34:34

      弱弱的问一句,起始位置为什么要-1

    • @ 2018-08-03 09:43:03

      好评,

    • @ 2019-03-16 10:44:33

      超级清楚

  • 4
    @ 2017-10-27 16:38:23

    简单区间DP
    25ms

    
    #include <queue>
    #include <cmath>
    #include <cctype>
    #include <vector>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int a[201];
    int f[201][201];
    int main()
    {
        int n,s=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            a[n+i]=a[i];
        }
        for(int i=n*2-1;i>=1;i--)
        {
            for(int j=i+1;j<2*n&&j-i<n;j++)
            {
                for(int k=i;k<=j-1;k++)
                {
                    f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
                }
                s=max(s,f[i][j]);
            }
        }
        printf("%d",s);
        return 0;
    }
    
    
  • 2
    @ 2014-08-14 10:05:56

    var
    i,j,k,sum,n:longint;
    a:array[1..101]of longint;
    f:array[1..2000,1..2000]of longint;
    function max(a,b:longint):longint;
    begin
    if a>b then
    exit(a)
    else
    exit(b);
    end;
    begin
    read(n);
    for i:=1 to n do
    f[i,i]:=0;
    for i:=1 to n do
    begin
    read(a[i]);
    a[i+n]:=a[i];
    end;
    for i:=2*n-3 downto 1 do
    for j:=i+2 to n+i do
    for k:=i+1 to j-1 do
    f[i,j]:=max(f[i,j],f[i,k]+f[k,j]+a[i]*a[k]*a[j]);
    for i:=1 to n do
    sum:=max(f[i,i+n],sum);
    writeln(sum);
    end.

  • 1
    @ 2018-07-19 11:48:20
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int head[1005],tail[1005],f[1005][1005];
    int main()
    {
        freopen("energy.in","r",stdin);
        freopen("energy.out","w",stdout);
        int i,j,k,x,maxn,n;
        cin>>n;
        cin>>head[1];
        for(i=2; i<=n; i++)
    {
        cin>>head[i];
        tail[i-1]=head[i];
    }
        tail[n]=head[1];
        for(i=n+1;i<=2*n-1;i++)
        {
            head[i]=head[i-n];
            tail[i]=tail[i-n];
        }
        for(x=1;x<=n;x++)//合并珠子数量
            for(i=1;i<=2*n;i++)//起始位置
        {
            j=i+x;
            for(k=i;k<j;k++)//最后两颗珠子合并位置
              f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);
        }
        maxn=0;
        for(i=1;i<=n;i++)
          if(f[i][n+i-1]>maxn)
            maxn=f[i][n+i-1];
        cout<<maxn<<endl;
        fclose(stdin);fclose(stdout);
    }
    //f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[i]*a[k+1]);
    //从i到j的最大能量=max(当前能量,从i到k的最大能量+从k+1到j的最大能量+两颗珠子合并释放的能量) 
    
  • 1
    @ 2017-10-30 15:47:33

    一道区间型(环形)DP
    其实相当于把整个项链double,在项链后面再接一根一模一样的

    石子合并矩阵连乘都很相似。
    首先项链是环状的,我们肯定要把它从某处断开,从哪断开呢?枚举断点即可。

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int a[201],dp[201][201],maxn,n;
    
    inline int read()//没有用的读入优化
    {
        int f=1,res=0;char ch = getchar();
        while(ch>'9'||ch<'0'){if(ch =='-')  f=-1;ch=getchar();}
        while(ch<='9'&&ch>='0') res=(res<<3)+(res<<1)+ch-'0',ch=getchar();
        return f*res;
     } 
    
    int main()
    {
        n=read();
        for(int i=1;i<=n;i++)
            a[i]=a[n+i]=read();//展开环
        for(int i=(n<<1)-1;i>=1;i--)
        {
            for(int j=i+1;j<(n<<1) && j-i < n;j++)
            {
                for(int k=i;k<=j-1;k++)//枚举断点
                {
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]);
                }
                maxn=max(maxn,dp[i][j]);
            }
        }
        printf("%d",maxn);
        return 0;
    }
    
  • 1
    @ 2017-10-16 19:03:35

    简单处理成环,之后简单DP.

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #define LL long long 
    using namespace std;
    template <class _T> inline void read(_T &_x) {
        int _t; bool _flag=false;
        while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
        if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
        while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
        if(_flag) _x=-_x;
    }
    const int maxn=105;
    int n;
    LL dp[maxn<<1][maxn<<1],ans;
    struct node{
        int l,r;
    }d[maxn<<1];
    
    
    int main(){
        read(n);
        for(int i=1;i<=n;i++){
            read(d[i].l);d[i+n].l=d[i].l;
            d[i-1].r=d[i+n-1].r=d[i].l;
        }
        for(int len=1;len<=n;len++){
            for(int l=1,r;(r=l+len-1)<2*n;l++){
                for(int k=l;k<r;k++){
                    dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+d[l].l*d[r].r*d[k].r);
                }
            }
        }
        for(int i=1;i<=n;i++){
            ans=max(ans,dp[i][i+n-1]);
        }
        printf("%lld",ans);
        
        return 0;
    }
    
  • 1
    @ 2017-04-06 23:47:57
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    int n,f[209][209],s[209],ans,i,j,k;
    
    int main()
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&s[i]);
            s[i+n]=s[i];
        }
        for(i=n*2-1;i>=1;i--)
            for(j=i+1;j<n*2&&j-i<n;j++)
            {
                for(k=i;k<j;k++)
                    f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+s[i]*s[k+1]*s[j+1]);
                ans=max(ans,f[i][j]);
            }
        printf("%d\n",ans);
        return 0;
    }
    
  • 0
    @ 2018-10-02 17:35:02
    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    int head[105];
    int tail[105];
    
    int f[105][105];
    
    int n;
    
    int main()
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", head + i);
        }
        for (int i = 0; i < n - 1; i++) {
            tail[i] = head[i + 1];
        }
        tail[n - 1] = head[0];
        for (int s = 1; s < n; s++) {
            for (int i = 0; i < n; i++) {
                int j = (i + s) % n;
                if (i < j) {
                    for (int k = i; k < j; k++) {
                        f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + head[i] * tail[k] * tail[j]);
                    }
                } else {
                    for (int k = i; k < j || k >= i; k++, k %= n) {
                        f[i][j] = max(f[i][j], f[i][k] + f[(k + 1)%n][j] + head[i] * tail[k] * tail[j]);
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < n; i++) {
            ans = max(ans, f[i][i-1]);
        }
        ans = max(ans, f[0][n-1]);
        printf("%d", ans);
        return 0;
    }
    
    
    
  • 0
    @ 2018-03-03 22:00:00

    环形区间动规,类比矩阵连乘,动规方程式:
    F(i,j)=M(i)*M(j)*M(k)+F(i,k)+F(k+1,j)
    CK()是用来处理越界数据的,省一点空间,虽然才10^4。

    #include<bits/stdc++.h>
    using namespace std;
    int n,M[101];
    long long int F[100][100];//以J为起点,K为终点的区间最优解 
    
    int CK(int a)
    {
        if(a>=n)
            return a-n;
        else
            return a;
    }
    
    int main()
    {
        cin >> n;
        for(int i=0;i<n;i++)
        {
            cin >> M[i];
            F[i][i]=0;
        }
        M[n]=M[0];long long int Mans=0;
        for(int i=1;i<n;i++)
        {//i表示规模,如i=1时表示有两个珠子,即i+1个珠子在区间内 
            for(int j=0;j<n;j++)
            {//j表示起点,终点为 CK(j+i)
                long long int ans=0;
                for(int k=0;k<i;k++)
                {//中间标记为M[j+k+1],前区间[j,j+k],后区间[j+k+1,j+i]
                    ans=max(ans,M[j]*M[CK(j+i+1)]*M[CK(j+k+1)]+F[j][CK(j+k)]+F[CK(j+k+1)][CK(j+i)]);
                }
                F[j][CK(j+i)]=ans;
                if(i==n-1)
                    Mans=max(Mans,ans);
            }
        }
        cout << Mans;
        return 0;
    }
    
  • 0
    @ 2017-09-08 08:32:18

    一个很简单的区间DP,主要是环变线,想说两点:
    1. 用专门的结构体存比较好理解。
    2. 答案区间是要尽可能枚举到最右边的,虽然最终答案的区间左端点必定是在【1,N】,但在逐级转移中也可能会出现【N+i,N+j】的一个最优贡献,要考虑到位。

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    struct BALL {
        int l, r;   
    };
    int N;
    BALL B[205];
    int A[105], F[205][205];
    int main () {
        
        scanf("%d", &N);
        for(int i=1; i<=N; i++) {
            scanf("%d", &A[i]);
            B[i].l=A[i], B[i-1].r=A[i];
        }
        B[N].r=A[1];
        for(int i=1; i<=N; i++) B[i+N]=B[i];
        for(int i=2; i<=N; i++)
            for(int l=1; l+i-1<=2*N; l++) {
                int r=l+i-1;
                for(int k=l; k<r; k++) 
                    F[l][r]=max(F[l][r], F[l][k]+F[k+1][r]+B[l].l*B[k].r*B[r].r);
            }  
        int ans=0;   
        for (int i=1; i<=N; i++)
            ans=max(ans, F[i][N+i-1]);
        printf("%d\n", ans);        
        return 0;  
          
    }
    
  • 0
    @ 2017-06-08 13:24:49
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    int main() {
        int n;
        cin >> n;
        int a[2 * n - 1];
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (i < n)
                a[i + n] = a[i];
        }
        int f[2 * n - 1][2 * n - 1];
        memset(f, 0, sizeof(f));
        for (int len = 2; len <= n; len++)
            for (int l = 0; l + len - 1 < 2 * n - 1; l++) {
                int r = l + len - 1;
                f[l][r] = 0;
                for (int k = l; k < r; k++)
                    f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + a[l] * a[k + 1] * a[r + 1]);
            }
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = max(ans, f[i][i + n - 1]);
        cout << ans << endl;
        return 0;
    }
    
  • 0
    @ 2017-01-31 15:23:36
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int n,f[200][200],ans=0;
    
    struct node1
    {
        int x,y;
    }a[200];
    
    int main()
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i].x);
        a[n].y=a[1].x;
        for (int i=1;i<n;i++)
        {
            a[i].y=a[i+1].x;
            a[i+n]=a[i];
        }
        memset(f,0,sizeof(f));
        for (int l=1;l<=n;l++)
            for (int i=1;i<2*n-l;i++)
                for (int j=i;j<i+l;j++)
                    f[i][i+l]=max(f[i][i+l],f[i][j]+f[j+1][i+l]+(a[i].x*a[j].y*a[i+l].y));
        for (int i=1;i<=n;i++)
            ans=max(ans,f[i][i+n-1]);
        printf("%d\n",ans);
    }
    
  • 0
    @ 2016-11-09 20:49:03

    #include <cstdio>
    #include <algorithm>
    #define M 110
    using std::max;

    int m=0,n,v[M],f[M][M]={0};

    int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&v[i]);
    for(int j=2;j<=n;j++)
    for(int i=0;i<n;i++)
    for(int k=1;k<j;k++)
    f[i][j]=max(f[i][j],f[i][k]+f[(i+k)%n][j-k]+v[(i+k)%n]*v[i]*v[(i+j)%n]);
    for(int i=0;i<n;i++)
    m=max(m,f[i][n]);
    printf("%d",m);
    return 0;
    }

  • 0
    @ 2016-10-23 17:47:03

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 680 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 680 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 680 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 676 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 680 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 680 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 680 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 680 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 680 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 680 KiB, score = 10
    Accepted, time = 60 ms, mem = 680 KiB, score = 100
    返回代码界面 | 关闭

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int n,f[209][209],a[209],ans=0;
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {scanf("%d",&a[i]);a[i+n]=a[i];}
    for(int i=n*2-1;i>=1;--i)
    {
    for(int j=i+1;j<n*2&&j-i<n;++j)
    {
    for(int k=i;k<j;k++)
    {
    f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
    }
    ans=max(ans,f[i][j]);
    }
    }
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2016-07-27 15:50:04

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<vector>
    #include<queue>
    #include<map>
    #include<set>
    #include<stack>
    #include<cstdlib>
    #include<string>
    #include<bitset>
    #include<iomanip>
    #define ll long long
    using namespace std;
    int n,sum,ans = 0;
    int a[205],f[205][205];
    int juhe(int i,int k,int j){
    sum = a[i] * a[k + 1] * a[j + 1];
    return sum;
    }
    int main(){
    //freopen("p1312.in","r",stdin);
    //freopen("p1312.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
    scanf("%d",&a[i]);
    a[i + n] = a[i];
    }
    for(int i = 1;i <= 2*n;i++)
    f[i][i] = 0;
    for(int j = 1;j < 2*n;j++)
    for(int i = j;i >= max(1,j - n + 1);i--){
    for(int k = i;k < j;k++){
    f[i][j] = max(f[i][j],f[i][k]+f[k+1][j]+juhe(i,k,j));
    }
    }

    for(int i = 1;i<=n;i++)
    ans=max(ans,f[i][i+n-1]);
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2016-06-13 13:06:39

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    using namespace std;
    const int N = 105;
    const int M = N << 1;
    int n,res = 0,head[M],f[M][M] = {0};
    int main()
    {
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
    scanf("%d",&head[i]);
    head[n + i] = head[i];
    }
    for(int p = 1;p < n;p++)
    for(int i = 1;i < ((n << 1) - 1);i++)
    for(int j = min(i + p,(n << 1) - 1),k = i;k < j;k++)
    f[i][j] = max(f[i][j],f[i][k] + f[k + 1][j] + head[i] * head[k + 1] * head[j + 1]);
    for(int i = 1;i <=n;i++)
    res = max(res,f[i][n + i - 1]);
    printf("%d\n",res);
    return 0;
    }

  • 0
    @ 2016-04-02 09:19:13

    多开1倍的数组,26行搞定
    #include <iostream>
    using namespace std;
    int n,a[205],b[205],f[205][205],x;
    int main()
    {
    cin >> n;
    for(int i = 1 ; i <= n ; i++ )
    {
    cin>>a[i];
    a[i+n]=a[i];
    }
    b[n]=a[1];
    for(int i = 1 ; i < n ; i++ )
    b[i]=b[i+n]=a[i+1];
    for(int c=1;c<n;c++)
    for(int i=1;i<=2*n-c;i++)
    {
    x=i+c;
    for(int j=i;j<x;j++)
    f[i][x]=max(f[i][x],f[i][j]+f[j+1][x]+a[i]*b[j]*b[x]);
    }
    for(int i=1;i<=n;i++)
    f[0][0]=max(f[i][i+n-1],f[0][0]);
    cout<<f[0][0];
    return 0;
    }

  • 0
    @ 2015-10-27 12:37:24

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int MAXN = 200 + 10;

    int a[MAXN], f[MAXN][MAXN];

    int main()
    {
    int n, ans = 0;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
    scanf("%d", &a[i]);
    a[i+n] = a[i];
    }
    for(int j=1; j<2*n; j++){
    for(int i=j; i>=max(1, j-n+1); i--){
    if(i == j) f[i][j] = 0;
    for(int k=i; k<j; k++)
    f[i][j] = max(f[i][j], f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
    }
    if(j >= n)
    ans = max(ans, f[j-n+1][j]);
    }
    printf("%d", ans);
    return 0;
    }

  • 0
    @ 2015-10-26 21:56:53

    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    int a[1000],f[1000][1000];
    int n;
    int main()
    {
    memset(f,0,sizeof(f));
    cin>>n;
    for(int i=1;i<=n;i++){
    cin>>a[i];
    a[i+n]=a[i];
    }
    int maxn=0;
    for(int i=2;i<=n+n;i++){
    for(int j=i-1;i-j<n&&j>=1;j--){
    for(int k=j;k<i;k++){
    f[j][i]=max(f[j][i],f[j][k]+f[k+1][i]+a[j]*a[k+1]*a[i+1]);
    }
    maxn=max(maxn,f[j][i]);
    }
    }
    //for(int i=1;i<=n;i++)maxn=max(maxn,f[i][n+i-1]);
    cout<<maxn;
    }
    只要将一条项链【1,n】连成【1,2n】的一条链即可

  • 0
    @ 2015-10-04 16:08:20

    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <iostream>
    using namespace std;
    int N=0;
    int mark[300];
    bool vis[300][300];
    long long d[300][300];
    long long max(long long &a,long long &b)
    {
    if(a>b) return a;
    else return b;
    }
    void init()
    {
    for(int i=0;i!=300;++i)
    for(int j=0;j!=300;++j) vis[i][j]=d[i][j]=0;
    }

    long long dp(int i,int j)
    {
    if(i==j) return 0;
    if(vis[i][j]) return d[i][j];
    for(int k=i;k<j;++k) d[i][j]=max(d[i][j],dp(i,k)+dp(k+1,j)+mark[i]*mark[k+1]*mark[j+1]);
    vis[i][j]=1;
    return d[i][j];
    }
    int main()
    {
    long long ans=0;
    scanf("%d",&N);
    for(int i=1;i<=N;++i)
    {
    scanf("%d",mark+i);
    mark[i+N]=mark[i];
    }
    mark[N+N+1]=mark[1];
    for(int i=1;i<=N;++i)
    {
    init();
    ans=max(ans,dp(i,i+N-1));
    }
    cout<<ans<<endl;
    return 0;
    }

信息

ID
1312
难度
4
分类
动态规划 | 环形DP 点击显示
标签
递交数
6303
已通过
2567
通过率
41%
被复制
8
上传者