区间Dp习题集

一.Problem - D - Codeforces

        （1）题目大意

        给定你两个数组A和B，你能够反转A的连续子序列一次，现在问你最多执行一次操作的情况下Ai * Bi的和最大是多少。

         （2）解题思路

                 由于n是5000，因此我们可一采用Dp来进行求解，我们枚举需要反转的区间l和r，预处理出一个前缀和，若此时反转l-r,那么我们能得到的答案就是s[l - 1] + s[n] - s[r + 1] + dp[l][r]。

        （3）代码实现

#include "bits/stdc++.h"
using namespace std;
const int N = 5e3 + 10;
long long f[N][N],a[N],pre[N],b[N];
long long dfs(int l,int r)
{
    if(l > r) return 0;
    if(l == r) return f[l][r] = a[l] * b[r];
    if(f[l][r]) return f[l][r];
    return f[l][r] = a[l] * b[r] + a[r] * b[l] + dfs(l + 1,r - 1);
}
void solve()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++) cin >> b[i];
    for(int i = 1;i <= n;i++) pre[i] += pre[i - 1] + a[i] * b[i];
    long long mx = 0;
    for(int i = 1;i <= n;i++) 
        for(int j = i;j <= n;j++) 
            mx = max(mx,pre[i - 1] + pre[n] - pre[j] + dfs(i,j));
    cout << mx << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    T = 1;
    while(T --) {
        solve();
    }
    return 0;
}

二.Problem - C - Codeforces

        （1）题目大意

                给你一个序列，每个ai的价值就是max(a1-ai) - min(a1-ai),现在让你求这个区间最后最小能变成多少，序列可以重新排列。

         （2）解题思路

                刚开始贪心搞了两发，发现情况有点多，讨论不完，因此改为区间dp，dp[i][j]表示i-j的最小的值是多少，状态转移方程为dp[i][j] = min(dp[i][j + i - 1],dp[i + 1][i + j]) + s[i + j] - s[i]。

        （3）代码实现

#include "bits/stdc++.h"
using namespace std;
const int N = 2e3 + 10;
long long n,dp[N][N],a[N];
void solve()
{
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1,a + 1 + n);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j + i <= n;j++) {
            int l = j,r = j + i;
            dp[l][r] = min(dp[l + 1][r],dp[l][r - 1]) + a[r] - a[l];
        }
    cout << dp[1][n] << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    T = 1;
    while(T --) {
        solve();
    }
    return 0;
}