一些环上的dp

发布于:2022-11-29 ⋅ 阅读:(337) ⋅ 点赞:(0)

解题方向:

环上的 d p dp dp解题方法一般分为两种:
1.找不同集合去覆盖全部的集合,跑两次 d p dp dp
2.破环成链。

休息时间

题意:

星球一天有 N N N个小时,一头牛每天要睡 B B B小时,在第 i i i个小时睡觉可以恢复 a [ i ] a[i] a[i]的体力。睡觉的时间可以分成若干段,但是每段的第一个小时是不恢复体力的。每一天的第 N N N个小时和下一天的第 1 1 1个小时是连续的,其只需在每 N N N个小时休息 B B B小时就够了,求可恢复的最多的体力。

思路:

显然,该题破环成链也可以做,但是时间复杂度太大。我们考虑一个简化的问题:第 N N N个小时和下一天的第 1 1 1个小时不相连。那么我们直接 f [ i , j , 0 / 1 ] f[i,j,0/1] f[i,j,0/1]表示前 i i i个小时休息了 j j j小时,且当前在不在休息。简单 d p dp dp即可。
我们可以把集合划分为两部分:
1.第 N N N个小时睡觉
2.第 N N N个小时睡觉
显然,我们的答案一定可以在其中之一取到。
我们仿照上述 d p dp dp跑两边即可,仅初始状态不一样。

code:

const int N = 4000 + 10, M = N * 2, mod = 998244353;

int n, m, a[N];
int f[2][N][2];

signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
	read(n), read(m);
	rep(i, 1, n) read(a[i]);
	//第N个小时不睡觉
	memset(f, -0x3f, sizeof f);
	int now = 1;
	f[0][0][0] = f[0][1][1] = 0;
	for(int i = 2; i <= n; i++) {
		for(int j = 0; j <= min(i, m); j++) {
			f[now][j][0] = max(f[now ^ 1][j][0], f[now ^ 1][j][1]);
			if(j) f[now][j][1] = max(f[now ^ 1][j - 1][0], f[now ^ 1][j - 1][1] + a[i]);
		}
		now ^= 1;
	}
	int ans = max(f[now ^ 1][m][0], f[now ^ 1][m][1]);
	//第N个小时睡觉
	memset(f, -0x3f, sizeof f);
	now = 1;
	f[0][1][1] = a[1];
	for(int i = 2; i <= n; i++) {
		for(int j = 0; j <= min(i, m); j++) {
			f[now][j][0] = max(f[now ^ 1][j][0], f[now ^ 1][j][1]);
			if(j) f[now][j][1] = max(f[now ^ 1][j - 1][0], f[now ^ 1][j - 1][1] + a[i]);
		}
		now ^= 1;
	}
	ans = max(ans, f[now ^ 1][m][1]);
	cout << ans << '\n';
	return 0;
}

ABC 251E:Takahashi and Animals

题意:

n n n个动物,每次可以花费 a [ i ] a[i] a[i]的代价给动物 i , i + 1 i,i+1 i,i+1喂一次食,花费 a [ n ] a[n] a[n] n , 1 n,1 n,1喂食。求最小代价给每个动物至少喂一次。

思路:

很明显,我们可以对集合进行如下划分:
1.动物 n , 1 n,1 n,1一起喂食
2.动物 n , 1 n,1 n,1不一起喂食
我们定义 f [ i , 0 / 1 ] f[i,0/1] f[i,0/1]表示前 i i i个动物中,当前动物是否和上一个动物一起喂食。
跑两边 d p dp dp即可。

code:

int n, a[N];
LL f[N][2]; // f[i][1/0]:前i个动物中,当前 是/否 是和上一个动物一起喂的

signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
	read(n);
    rep(i, 1, n) read(a[i]);
    //第1个动物不和第n个一起喂食
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for(int i = 2; i <= n; i++) {
        f[i][1] = min(f[i - 1][1] + a[i - 1], f[i - 1][0] + a[i - 1]);
        f[i][0] = f[i - 1][1];
    }
    LL ans = f[n][1];
    //第1个动物和第n个一起喂食
    memset(f, 0x3f, sizeof f);
    f[1][1] = a[n];
    for(int i = 2; i <= n; i++) {
        f[i][1] = min(f[i - 1][1] + a[i - 1], f[i - 1][0] + a[i - 1]);
        f[i][0] = f[i - 1][1];
    }
    ans = min(ans, min(f[n][1], f[n][0]));
    cout << ans << '\n';
	return 0;
}

黑龙江省赛G:Chevonne’s Necklace

题意:

n n n个珍珠围成一个项链,每颗珍珠有一个权值 a [ i ] a[i] a[i],代表选择这个珍珠后将其后面 a [ i ] − 1 a[i]-1 a[i]1个一起删掉,如果不够 a [ i ] − 1 a[i]-1 a[i]1个,则不能选。删掉一些珍珠后,其它的继续合并成为新的项链。问最多可以删掉多少个珍珠,且在最多个数的前提下,删除的方案。

思路:

引理:如果集合中的珍珠的 a [ i ] a[i] a[i]的和 s u m ≤ n sum\leq n sumn,则该集合一定合理。
那么就转化为了 0 / 1 0/1 0/1背包问题。

本文含有隐藏内容,请 开通VIP 后查看