题目链接: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;
}
标签:int,mi,cf,num,mx,dp,typedb2023
From: https://www.cnblogs.com/xjwrr/p/17364316.html