cf-typedb2023-C

xjwrr / 2023-05-03 / 原文

题目链接：https://codeforces.com/problemset/problem/1787/C

我是sb，这种dp都没想到。。。

思路：首先得发现一个性质(贪心)，每个数拆成的两个数一定是一个最大的(尽可能)，另一个最小(尽可能)。这点不难证明，随便写写式子可得证。由于每个数只会影响相邻的两个数，所以我们可以dp算答案。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int num[N];
int mx[N],mi[N];
long long dp[N][2];
void solve(){
    int n,k;
    cin>>n>>k;
    for (int i=1;i<=n;i++) {
        cin>>num[i];
        if (num[i]>=2*k) mx[i] = num[i]-k,mi[i] = k;
        else if (num[i]>=k) mx[i] = k,mi[i] = num[i]-k;
        else mx[i] = num[i],mi[i] = 0;
    }
    for (int i=2;i<n;i++){
        if (i==2){
            dp[i][1] = 1ll*num[1]*mx[i];
            dp[i][0] = 1ll*num[1]*mi[i];
        }else{
            dp[i][1] = min(dp[i-1][0]+1ll*mx[i-1]*mx[i],dp[i-1][1]+1ll*mi[i-1]*mx[i]);
            dp[i][0] = min(dp[i-1][0]+1ll*mx[i-1]*mi[i],dp[i-1][1]+1ll*mi[i-1]*mi[i]);
        }
    }
    long long ans = min(dp[n-1][0]+1ll*mx[n-1]*num[n],dp[n-1][1]+1ll*mi[n-1]*num[n]);
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    T = 1;
    cin>>T;
    while(T--) solve();
    return 0;
}