本文主要是介绍线性dp：CF1287(C) Garland，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
题意：一串绳子上又n个编号为1到n的灯泡（乱序），其中几个掉落，让我们把掉落的灯泡安装回去，使绳子的权值最小。
相邻两个为不同奇偶性为一个权值，如1，4，2，3，5的权值为2；而1，3，5，7，6，4，2的权值为1.
思路：因为这是线性dp，开一个四维数组dp[i][j][k][x]来表示第i个位置的权值，j表示在第i个位置以前安装了多少个奇数灯泡，k表示在第i个位置以前安装了多少个偶数灯泡，x=1表示第i个位置为奇数灯泡，x=0表示第i个位置为偶数灯泡。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=105;
int dp[N][55][55][3];
int sum[N],a[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;int odd=n-n/2,even=n/2;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]){if(a[i]&1) odd--;else even--;}else sum[i]++;}memset(dp,INF,sizeof dp);for(int i=1;i<=n;i++) sum[i]+=sum[i-1];//统计i位置以前空位的数量if(a[1]){//初态的模拟if(a[1]&1) dp[1][0][0][1]=0;else dp[1][0][0][0]=0;}else{dp[1][1][0][1]=0;dp[1][0][1][0]=0;}for(int i=2;i<=n;i++){for(int j=0;j<=odd;j++){int k=sum[i]-j;if(j>sum[i]||k>sum[i]) continue;if(a[i]){if(a[i]&1) dp[i][j][k][1]=min(dp[i-1][j][k][0]+1,dp[i-1][j][k][1]);else dp[i][j][k][0]=min(dp[i-1][j][k][1]+1,dp[i-1][j][k][0]);}else{dp[i][j][k][0]=min(dp[i-1][j][k-1][0],dp[i-1][j][k-1][1]+1);dp[i][j][k][1]=min(dp[i-1][j-1][k][0]+1,dp[i-1][j-1][k][1]);}}}int ans=0;if(a[n]){if(a[n]&1) ans=dp[n][odd][even][1];else ans=dp[n][odd][even][0];}else ans=min(dp[n][odd][even][0],dp[n][odd][even][1]);cout<<ans<<endl;return 0;
}
这篇关于线性dp：CF1287(C) Garland的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
