DP(10%状压+90%思维)
题意：有N个街区从左到右依次排列，每个街区有一盏路灯，打开第i个路灯需要wi的成本，打开一盏路灯可以使该位置，该位置左侧，该位置右侧的街区被照亮，你可以交换K次任意路灯的wi成本值。问要使N个街区都被照亮所需要的最小成本是多少?
如果不考虑换路灯的操作（k=0）那么这题是一道比较简单的DP（状压DP）。我们用二进制数表示前一个路灯和当前路灯的开关状态。00(0)代表都关闭，01(1)代表当前的灯开了而前一个灯没开，10(2)，11(3)以此类推。那么易得
DP[i][0]=dp[i-1][2]
Dp[i][1]=min(dp[i-1][0],dp[i-1][2])+w[i];
dp[i][2]=min(dp[i-1][1],dp[i-1][3]);
dp[i][3]=min(dp[i-1][1],dp[i-1][3])+w[i];
好，现在我们就要考虑k>0的情况。
为了使成本最小化，我们肯定使拿w值较大的开着的路灯去换w值较小的关闭的路灯。假设我们当前枚举到了第i个路灯，对于状态01，11，我们可以拿一个关闭的路灯和当前路灯交换，对于状态00，10，我们可以拿一个开着的路灯和当前路灯交换。那么问题来了，我们如何在DP的过程中确定，当前路灯和哪一个路灯换呢？其实这个问题根本不需要解决，我们只要知道哪些关闭的路灯被拿出来和哪些开着交换就可以了，不需要具体的交换方式。
所以对于状态00，10，我们可以把当前路灯（处于关闭状态）拿出来和开着的路灯交换，
也就是虽然我们不在此时开这个灯，但我们也算上开这灯的成本。对于状态01，11，我们可以把当前路灯和关闭的路灯交换。也就是虽然我们开了这盏灯，但我们不算上他的开灯成本。
我们可以升级我们的DP数组
Dp[i][s][j][p]
I:路灯
s:状态
j:有j盏开着的灯被用于交换
p:有p盏关闭的灯被用于交换
那么有：
dp[i][0][j][p]=dp[i-1][2][j][p];
if(p>0){ //补
dp[i][0][j][p]=min(dp[i][0][j][p],dp[i-1][2][j][p-1]+w[i]);
}
dp[i][1][j][p]=min(dp[i-1][0][j][p],dp[i-1][2][j][p])+w[i];
if(j>0){ //缺
dp[i][1][j][p]=min(dp[i][1][j][p],min(dp[i-1][0][j-1][p],dp[i-1][2][j-1][p]));
}
dp[i][2][j][p]=min(dp[i-1][1][j][p],dp[i-1][3][j][p]);
if(p>0){ //补
dp[i][2][j][p]=min(dp[i][2][j][p],min(dp[i-1][1][j][p-1],dp[i-1][3][j][p-1])+w[i]);
}
dp[i][3][j][p]=min(dp[i-1][1][j][p],dp[i-1][3][j][p])+w[i];
if(j>0){ //缺
dp[i][3][j][p]=min(dp[i][3][j][p],min(dp[i-1][1][j-1][p],dp[i-1][3][j-1][p]));
}
AAAACCCC代代代代码码码码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k;
long long w[250001];
// 缺 补
long long dp[250001][4][10][10];
int main(){
scanf("%d",&n);
scanf("%d",&k);
memset(dp,0x3f3f,sizeof(dp));
long long ans=1e16;
for(int i=1;i<=n;i++){
scanf("%lld",&w[i]);
}
dp[1][0][0][0]=0;
dp[1][0][0][1]=w[1];
dp[1][1][0][0]=w[1];
dp[1][1][1][0]=0;
for(int i=2;i<=n;i++){
for(int j=0;j<=k;j++){
for(int p=0;p<=k;p++){
dp[i][0][j][p]=dp[i-1][2][j][p];
if(p>0){ //补
dp[i][0][j][p]=min(dp[i][0][j][p],dp[i-1][2][j][p-1]+w[i]);
}
dp[i][1][j][p]=min(dp[i-1][0][j][p],dp[i-1][2][j][p])+w[i];
if(j>0){ //缺
dp[i][1][j][p]=min(dp[i][1][j][p],min(dp[i-1][0][j-1][p],dp[i-1][2][j-1][p]));
}
dp[i][2][j][p]=min(dp[i-1][1][j][p],dp[i-1][3][j][p]);
if(p>0){ //补
dp[i][2][j][p]=min(dp[i][2][j][p],min(dp[i-1][1][j][p-1],dp[i-1][3][j][p-1])+w[i]);
}
dp[i][3][j][p]=min(dp[i-1][1][j][p],dp[i-1][3][j][p])+w[i];
if(j>0){ //缺
dp[i][3][j][p]=min(dp[i][3][j][p],min(dp[i-1][1][j-1][p],dp[i-1][3][j-1][p]));
}
}
}
}
// for(int sb=0;sb<=k;sb++){
// for(int i=1;i<=n;i++){
// for(int j=0;j<4;j++){
// cout<<dp[i][j][sb][sb]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
// }
for(int i=1;i<3;i++){
for(int j=0;j<=k;j++){
ans=min(ans,dp[n][i][j][j]);
}
}
cout<<ans<<endl;
}腾讯云开发者
