[abc]AtCoder Beginner Contest 251 E - Takahashi and Animals

t a g : tag : tag:线性dp 环形问题
传送门 :
题意 :
有 N N N只猫,饲养 i i i只猫需要花费 A i A_i Ai​,选中饲养第 i i i只猫会同时顺带饲养第 i + 1 i+1 i+1猫,对于 n n n饲养的时候会顺带 1 1 1,询问每只猫都至少饲养到一次的最小花费

思路 :
显然的如果只是线性的问题的话,我们直接考虑动态规划

状态表示 :
f [ i ] [ 1 ] = [ i − 1 ] [ 2 ] f[i][1] = [i-1][2] f[i][1]=[i−1][2] 不选择饲养当前的猫
f [ i ] [ 2 ] = m i n ( f [ i − 1 ] [ 1 ] , f [ i − 1 ] [ 2 ] ) + w [ i ] f[i][2]=min(f[i-1][1],f[i-1][2])+w[i] f[i][2]=min(f[i−1][1],f[i−1][2])+w[i] 选择饲养当前的猫

因为成环,所以我们单独对 i = 1 i=1 i=1进行考虑

对于 f [ 1 ] [ 1 ] f[1][1] f[1][1]显然只有两个初始值

f [ 1 ] [ 1 ] = 0 f[1][1] =0 f[1][1]=0 第 n n n只猫饲养
f [ 1 ] [ 1 ] = I N F f[1][1] =INF f[1][1]=INF 第 n n n只猫没有饲养

而对于 f [ 1 ] [ 2 ] f[1][2] f[1][2]始终都是 w [ 1 ] w[1] w[1]

因此我们对于这两种初始状态都跑一遍即可

code :

ll f[N][3];
int n;
int w[N];

void solve(){
	cin>>n;
	
	for(int i=1;i<=n;i++) cin>>w[i];
	ll ans = 1e18;
	
	for(int p = 1 ;p<=2; p ++ ){
		//2表示饲养 1表示不饲养
		if(p == 1) f[1][1] = 0 , f[1][2] = w[1];
		else f[1][1] = INF , f[1][2] = w[1];
		
		for(int i=2;i<=n;i++){
			f[i][1] = f[i-1][2];
			f[i][2] = min(f[i-1][1],f[i-1][2]) + w[i];
		}
		
		if(p == 1)ans = f[n][2];
		else ans = min({ans,f[n][1],f[n][2]});
		
	}
	
	cout<