题解

5 条题解

  • 5
    @ 2017-09-27 15:40:52

    简单DP
    dp[i][j]表示i到j取到的最优值,用dp[i+1][j]或dp[i][j-1]来更新,前缀和优化一下。
    输入不要记录,不然会MLE

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    const int maxn=1e4+5;
    
    int n;
    int a,sum[maxn],dp[maxn][maxn];
    
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a);
            dp[i][i]=a;
            sum[i]=sum[i-1]+a;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j+i<=n;j++){
                dp[j][j+i]=sum[i+j]-sum[j-1]-min(dp[j+1][j+i],dp[j][j+i-1]);
            }
        }
        printf("%d",dp[1][n]);
        
        
        
        return 0;
    }
    
  • 1
    @ 2018-08-20 09:10:46
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=10005;
    int f[MAXN][MAXN];
    int s[MAXN];
    int a[MAXN];
    int n;
    
    void init()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i],s[i]=s[i-1]+a[i];
        for(int i=1;i<=n;i++)
            f[i][i]=a[i];
    }
    
    int main()
    {
        init();
        for(int l=1;l<=n-1;l++)
            for(int i=1;i<=(n-l);i++)
            {
                int j=i+l;
                f[i][j]=(s[j]-s[i-1])-min(f[i+1][j],f[i][j-1]);
            }
        cout<<f[1][n]<<endl;
    }
         
    
  • 0
    @ 2016-08-16 17:53:17

    都是巨啊,我蒟蒻只会分类讨论4000ms+,第一次还无聊到开两个数组致MLE
    ```c++
    #include <bits/stdc++.h>
    using namespace std;

    int dp[10005][10005];
    int n;
    int a[10005];
    int dfsj(int,int);
    int dfsy(int,int);

    int dfsj(int i, int j)
    {
    if (i == j) return a[i];
    if (dp[i][j] != -1) return dp[i][j];
    return dp[i][j] = max(dfsy(i, j-1)+a[j], dfsy(i+1, j)+a[i]);
    }

    int dfsy(int i, int j)
    {
    if (i == j) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    return dp[i][j] = min(dfsj(i, j-1), dfsj(i+1, j));
    }

    int main()
    {
    memset(dp,-1,sizeof dp);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    scanf("%d", &a[i]);
    cout << dfsj(1, n) << endl;
    return 0;
    }

  • 0
    @ 2016-04-03 22:29:17

    标答:
    c++
    #include <iostream>
    using namespace std;
    int n,a[10001],f[10001][10001],g[10001];
    int dfs(int m,int n)
    {
    if(f[m][n]>0)
    return f[m][n];
    if(m==n)
    return f[m][n]=a[m];
    return f[m][n]=max(g[n-1]-g[m-1]-dfs(m,n-1)+a[n],a[m]+g[n]-g[m]-dfs(m+1,n));
    }
    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    g[i]=g[i-1]+a[i];
    cout<<dfs(1,n);
    return 0;
    }

  • -1
    @ 2016-05-07 22:04:06

    f[l][r]表示 取l到r的数 先手取的数之和 比 后手的 最多 多 多少
    f[l][l]=a[l]
    f[l][r]=(a[l]-f[l+1][r],a[r]-f[l][r-1])
    ans=(f[1][n]+sum)/2

    递推比记忆化搜索快很多
    时间约缩短了60%

    使用int足矣

    #include<cstdio>
    #include<algorithm>
    #define fo(i,a,b) for(int i=a;i<=b;i++)
    using namespace std;
    int n,a[10005],f[10005][10005],sum;
    int main(){
    scanf("%d",&n);
    fo(i,1,n){
    scanf("%d",&a[i]);
    sum+=a[i];
    }
    fo(i,1,n)
    f[i][i]=a[i];
    fo(i,1,n-1)//i表示块的长度
    fo(j,1,n-i){//j表示起点位置
    f[j][i+j]=max(a[j]-f[j+1][i+j],a[i+j]-f[j][i+j-1]);
    }
    printf("%d\n",(sum+f[1][n])>>1);
    return 0;
    }

  • 1

信息

ID
1991
难度
7
分类
动态规划 点击显示
标签
(无)
递交数
228
已通过
52
通过率
23%
被复制
2
上传者