CF1221D Make The Fence Great Again

题意

题目大意是要让一连串连续的数字左右相邻两个两两不同，如果相同可以改高度，改的高度代价输入已知

解法

首先我们可以看到这应该就是一个DP,数据范围也不大不需要带优化(带优化的我现在也不会).我们观察发现一个点最多更改两次,然后我们进行转移即可也就是用当前的点推下一个点,如果当前的点更改0,1,2次和下一个点更改0,1,2次有不同的话那么取min转移.具体看代码吧

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300005;
ll f[N][4],a[N],b[N];
int main()
{
	ll t;
	scanf("%lld",&t);
	while(t--)
	{
		ll n,m;
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)
		scanf("%lld%lld",&a[i],&b[i]);
		for(int i=0;i<=n;i++)
		f[i][0]=f[i][1]=f[i][2]=m=1LL<<60;
		a[0]=-m;
		f[0][0]=0;
		for(int i=0;i<n;i++)
		for(int j=0;j<=2;j++)
		{
			if(f[i][j]==m)
			continue;
			for(int k=0;k<=2;k++)
			if(a[i]+j!=a[i+1]+k)
			f[i+1][k]=min(f[i+1][k],f[i][j]+k*b[i+1]);
		}
		printf("%lld\n",min(f[n][0],min(f[n][1],f[n][2])));
	}
}