[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>w[i];
	ll ans = 1e18;
	
	for(int p = 1 ;p