• 前言
• 题目大意
• 思路
• 代码
• 总结

前言

这个笔记就写一下这个题的类型吧，思路可以用这个跟我之前整理的区间合并类套路和区间多情况套路结合起来看。

题目大意

好长，懒得删了。传送门

思路

本题的关键在于每一次做dp公式时不能只把眼光放到单独的区间中，要考虑移动时整体发生的价值改变。

代码

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const ll MAXN=55;
ll n,c,a[MAXN],f[MAXN],dp[MAXN][MAXN][2];
ll value(ll i,ll j,ll l,ll r){
    return (a[j]-a[i])*(f[l]+(f[n]-f[r-1]));
}
int main(){
    memset(dp,0x3f,sizeof(dp));
    scanf("%lld%lld",&n,&c);
    for (int i = 1; i <=n ; ++i) {
        ll b;
        scanf("%lld%lld",&a[i],&b);
        f[i]=f[i-1]+b;
    }
    dp[c][c][0]=dp[c][c][1]=0;
    for (int r = c; r <=n ; ++r) {
        for (int l = r-1; l >=1 ; --l) {
            dp[l][r][0]= min(dp[l+1][r][0]+ value(l,l+1,l,r+1),dp[l+1][r][1]+ value(l,r,l,r+1));
            dp[l][r][1]= min(dp[l][r-1][1]+ value(r-1,r,l-1,r),dp[l][r-1][0]+ value(l,r,l-1,r));
        }
    }
    cout<<min(dp[1][n][0],dp[1][n][1])<<endl;
    return 0;
}

总结

我把它叫做区间整体问题吧。