GESP7级第14次认证编程题[消消乐]

编程题第二题【消消乐】

    这是一道区间动态规划的题目，每一次选择可以加上[i-1]和[i+1]的值，但是要删去i，请问怎么
选择可是值最大。首先要找出动态规划方程式(状态转移方程式)，我们要用到三层for循环，第一行
len是规定最右边的值(及r的值)，第二行l和r是范围，l为1，r为len(就是1-n)，第三行为k，表示l-r
中的一个值。

状态转移方程式

    应为是加上左边和右边的值，所以是dp[l][r]=dp[l][k-1]+dp[k+1][r]+a[l-1]+a[r+1]，其中还有max
所以最终为dp[l][r]=max(dp[l][r],dp[l][k-1]+dp[k+1][r]+a[l-1]+a[r+1])，其中dp[l][r]表示l-r区间中
所得的最大分数。

70%

#include<bits/stdc++.h>
using namespace std;
int n,a[110],dp[110][110];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        for(int l=1,r=i;r<=n;l++,r++){
            for(int k=l;k<=r;k++){
                dp[l][r]=max(dp[l][r],dp[l][k-1]+dp[k+1][r]+a[l-1]+a[r+1]);
            }
        }
    }
    cout<<dp[1][n];
}

为啥呢么是70%呢，应为数据范围，所以应该是long long，不是int。

AC代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[110],dp[110][110];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        for(int l=1,r=i;r<=n;l++,r++){
            for(int k=l;k<=r;k++){
                dp[l][r]=max(dp[l][r],dp[l][k-1]+dp[k+1][r]+a[l-1]+a[r+1]);
            }
        }
    }
    cout<<dp[1][n];
}

祝大家成功通过7级