2016 ACM/ICPC Asia Regional Shenyang Online 1009 QSC and Master 区间dp

QSC and Master 区间dp

状态定义： dp[i][j][u]  u == 1 时表示 当端点 i， j 进行合并时(取出 val[i] 、 val[j] 时)

或 i < k < k+1 < j， key[i] 和 key[k] 可以合并 且key[k+1] 和 key[j]合并的， 区间 [i, j]内的最大价值；

u == 0 时表示 当端点 i， j 不进行合并时(不取出 val[i] 、 val[j] 时) 的 区间 [i, j]内的最大价值；

初始化：全部初始化为 0；

边界： 当 j - i == 1 时 如果可以合并 则 dp[i][j][1] = val[i] + val[j]；

状态转移方程：如果 key[i], key[j] 可以组合， 则 如果 dp[i + 1][j - 1][1] > 0 则 dp[i][j][1] = max(dp[i][j][1], dp[i+1][j-1][1] + val[i] + val[j]);

然后对于 区间划分 k = i ~ j

dp[i][j][0] = max(dp[i][j][0], max(dp[i][k][0], dp[i][k][1]) + max(dp[k+1][j][1] , dp[k+1][j][0]));
if(dp[i][k][1] > 0 && dp[k+1][j][1] > 0) dp[i][j][1] = max(dp[i][j][1], dp[i][k][1] + dp[k+1][j][1]);

接着是对于u == 0时的转移(即keyi keyj 能合并时可以选择不合并)

dp[i][j][0] = max(dp[i][j][0], max(dp[i+1][j-1][1], dp[i+1][j-1][0]));

如果 key[i], key[j] 不能合并， 则
if(dp[i+1][j-1][1] > 0){
dp[i][j][0] = max(dp[i][j][0], max(dp[i+1][j-1][1], dp[i+1][j-1][0]));
for(k = i; k < j; k++){
dp[i][j][0] = max(dp[i][j][0], max(dp[i][k][0], dp[i][k][1]) + max(dp[k+1][j][1] , dp[k+1][j][0]));
if(dp[i][k][1] > 0 && dp[k+1][j][1] > 0) dp[i][j][1] = max(dp[i][j][1], dp[i][k][1] + dp[k+1][j][1]);
}

}
else{
dp[i][j][0] = max(dp[i][j][0], dp[i+1][j-1][0]);
for(k = i; k < j; k++){
dp[i][j][0] = max(dp[i][j][0], max(dp[i][k][0], dp[i][k][1]) + max(dp[k+1][j][1] , dp[k+1][j][0]));
if(dp[i][k][1] > 0 && dp[k+1][j][1] > 0) dp[i][j][1] = max(dp[i][j][1], dp[i][k][1] + dp[k+1][j][1]);
}
}

复杂度 O(n^3)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 3e2 + 8;

LL key[maxn], val[maxn], dp[maxn][maxn][2];

inline LL gcd(LL a, LL b)
{
    return b == 0 ? a : gcd(b, a % b);
}

inline bool check(LL a, LL b)
{
    return gcd(a, b) != 1;
}

int main()
{
    #ifdef LOCAL
    freopen("1009.txt", "r", stdin);
    //freopen("1009.out", "w", stdout);
    #endif // LOCAL
   // ios::sync_with_stdio(false); cin.tie(0);

    LL T, n;
    cin >> T;
    while(T--){
        memset(dp, 0, sizeof dp);
        cin >> n;
        for(int i = 0; i < n; i++){ cin >> key[i];
        }
        for(int i = 0; i < n; i++){ cin >> val[i];
        }

        LL i, j, k, ans = 0, x, y;
        for(i = n - 1; i >= 0; i--){
            for(j = i + 1; j < n; j++){ if(check(key[i], key[j])){ if(j - i > 2){
                        if(dp[i+1][j-1][1] > 0){
                            dp[i][j][1] = max(dp[i][j][1], dp[i+1][j-1][1] + val[i] + val[j]);
                        }
                        for(k = i; k < j; k++){ dp[i][j][0] = max(dp[i][j][0], max(dp[i][k][0], dp[i][k][1]) + max(dp[k+1][j][1] , dp[k+1][j][0])); if(dp[i][k][1] > 0 && dp[k+1][j][1] > 0) dp[i][j][1] = max(dp[i][j][1], dp[i][k][1] + dp[k+1][j][1]);
                        }
                        dp[i][j][0] = max(dp[i][j][0], max(dp[i+1][j-1][1], dp[i+1][j-1][0]));
                    }
                    else if(j - i == 1) dp[i][j][1] = val[i] + val[j];
                }

                if(j - i > 2){
                    if(dp[i+1][j-1][1] > 0){
                        dp[i][j][0] = max(dp[i][j][0], max(dp[i+1][j-1][1], dp[i+1][j-1][0]));
                        for(k = i; k < j; k++){ dp[i][j][0] = max(dp[i][j][0], max(dp[i][k][0], dp[i][k][1]) + max(dp[k+1][j][1] , dp[k+1][j][0])); if(dp[i][k][1] > 0 && dp[k+1][j][1] > 0) dp[i][j][1] = max(dp[i][j][1], dp[i][k][1] + dp[k+1][j][1]);
                        }

                    }
                    else{
                        dp[i][j][0] = max(dp[i][j][0], dp[i+1][j-1][0]);
                        for(k = i; k < j; k++){ dp[i][j][0] = max(dp[i][j][0], max(dp[i][k][0], dp[i][k][1]) + max(dp[k+1][j][1] , dp[k+1][j][0])); if(dp[i][k][1] > 0 && dp[k+1][j][1] > 0) dp[i][j][1] = max(dp[i][j][1], dp[i][k][1] + dp[k+1][j][1]);
                        }
                    }
                }
                else if(j - i == 1) dp[i][j][0] = 0;  //这行可以忽略 ^_^
                //*/
                ans = max(ans, max(dp[i][j][0], dp[i][j][1]));
            }

        }

        //cout << dp[0][n-1][0] << " " << dp[0][n-1][1]<< endl; if(ans > 0) cout << ans << "n";
        else cout << 0 << "n";
    }

    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx