思维

https://codeforces.com/gym/102059/problem/G

题意：

一条街上一共 N 个点，需要在某些点上建路灯，使得整条街被照亮，一个路灯可以照亮左右两个点，每个点都有一个建路灯的花费。

现在你还有 K次机会，可以交换两个路灯的建造费用，求使得整条街被照亮的最小花费。( 1 ≤ N ≤ 250000 , 0 ≤ k ≤ 9 )

分析：

如果这道题没有 K 次交换路灯花费的操作的话，问题将会变得简单很多，只需要记录每个点某尾和前一个点的状态即可递推求解。

发现如果两灯交换位置 一定是一个亮一个不亮 如果两个灯都是亮的 就没必要进行交换的操作

因此如果当前位置需要亮 但是我们不要当前的灯亮 我们就先欠着 等着后面亮的灯与之交换即可

同理如果当前位置不需要亮 我们可以交换前面我们欠着的灯还上

当然也可以先还再欠

于是设计dp[i][j][o][0\1\2\3] 最后一维用二进制表示最后两个位置的亮灭状态 前i个位置 欠了j个 还了o个

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
#define int ll
const int maxn=250005;
int dp[maxn][10][10][4],a[maxn]; // 0-00 1-01 2-10 3-11
int n,k;
void solve();
signed main(){
	int T;T=1;
	while(T--)solve();
     return 0;
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	memset(dp,0x3f,sizeof(dp));
	dp[0][0][0][2]=0;//欠了j个 还了o个 
	for(int i=1;i<=n;i++)
		for(int j=0;j<=k;j++)
			for(int o=0;o<=k;o++){
				dp[i][j][o][0]=dp[i-1][j][o][2];
				dp[i][j][o][1]=min(dp[i-1][j][o][0],dp[i-1][j][o][2])+a[i];
				dp[i][j][o][2]=min(dp[i-1][j][o][1],dp[i-1][j][o][3]);
				dp[i][j][o][3]=min(dp[i-1][j][o][1],dp[i-1][j][o][3])+a[i];
				if(j>0){
					dp[i][j][o][1]=min(dp[i][j][o][1],min(dp[i-1][j-1][o][0],dp[i-1][j-1][o][2]));
					dp[i][j][o][3]=min(dp[i][j][o][3],min(dp[i-1][j-1][o][1],dp[i-1][j-1][o][3]));
				}
				if(o>0){
					dp[i][j][o][0]=min(dp[i][j][o][0],dp[i-1][j][o-1][2]+a[i]);
					dp[i][j][o][2]=min(dp[i][j][o][2],min(dp[i-1][j][o-1][1],dp[i-1][j][o-1][3])+a[i]);
				}
			
	}
	ll ans=1e17; 
	for(int i=0;i<=k;i++)
	ans=min(min(ans,dp[n][i][i][1]),min(dp[n][i][i][2],dp[n][i][i][3]));
	cout<<ans;
}