2019-7题解综合2——DP

siundiy

2019-08-04

7.29 “简单”DP

luogu P2467 [SDOI2010]地精部落

题目大意

一个序列符合要求，当且仅当其是一个$1 \sim n$的排列，且每一个$a[i]$

满足$a[i-1]\le a[i]$且$a[i]\ge a[i+1]$

或者满足$a[i-1]\ge a[i]$且$a[i]\le a[i+1]$

求长度为$n$的合法序列方案数

大体思路

神仙题。。。。

显然有以下性质：

1.当$i$与$i+1$不相邻时，交换$i$与$i+1$仍会得到一个合法的解

如:$3 2 4 1 5 \rightarrow 3 1 4 2 5$

2.一串序列$a[i]$，$i\in [1,n]$满足条件时，则$(i+1)-a[i]$亦满足条件

如:$3 2 4 1 5 \rightarrow 3 4 2 5 1$

3.满足条件的序列具有对称性

如:$3 2 4 1 5 \rightarrow 5 1 4 2 3$

则设$dp[i][j]$表示当前为前$i$个数的排列，且首位是$j$且为山峰的方案数。

$\! \begin{split} & 由性质1可知: \!\begin{cases} \text{当$j$与$j-1$不相邻时，$dp[i][j]=dp[i][j-1]$}\\ \end{cases}\\ & 由性质2可知: \!\begin{cases} \text{首位做山峰的方案数=首位做山谷的方案数}\\ \downarrow \\ \text{(也就是说最后的答案是$2*\sum_{i=1}^n dp[n][i]$)}\\ \\ \text{当$j$与$j-1$相邻时，}\\ \text{方案数即为$i-1$个数，$j-1$为首位且为山谷的方案数}\\ \text{$\downarrow$}\\ \text{即$dp[i][j]=dp[i-1][(i-1+1)-(j-1)]$} \end{cases} \end{split}$

综上，$dp[i][j]=dp[i][j-1]+dp[i-1][i-j+1]$

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, p;
long long ans;
long long dp[2][4300];
int main(){
	scanf("%d%d", &n, &p);
	dp[0][2] = 1;
	for(int i = 3; i <= n; ++i){
		for(int j = 2; j <= i; ++j){
			dp[i & 1][j] = (dp[i & 1][j - 1] + dp[(i - 1) & 1][i - j + 1]) % p;
		}
	}
	for(int i = 1; i <= n; ++i){
		ans = ans + dp[n & 1][i] % p;
	}
	printf("%lld\n", (ans << 1) % p);
	return 0;
}

luogu P2519 [HAOI2011]problem a

题目传送门

题目大意

一次考试共有$n$个人参加，第$i$个人说：“有$ai$个人分数比我高，$bi$个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)

大体思路

先进行补集转化，目标变成求说真话的人数。
有$ai$个人分数比我低，$bi$个人分数比我高，就意味着$[ai+1,n-bi-1]$是相同的数。

问题转化为使$k$段区间不重叠且权值和最大。按照右端点排序之后dp即可。
几点细节:

1.合法解可以有完全重合的区间，但是一段区间最多只能有区间长度个说真话的人。

2.要特判$ai \ge bi$的情况

设$f[i]$表示当前为第$i$位的区间最大值，则

$f[i]=max(f[i-1],f[L[j]-1]+w[j]) (R[j]==i)$

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
#define gc ch = getchar()
int read(){
	int ret = 0, f = 1; char gc;
	while(!isdigit(ch) && (ch ^ '-'))gc;
	if(!(ch ^ '-'))f = -1, gc;
	while(isdigit(ch)){ret = (ret << 3) + (ret << 1) + (ch ^ '0'), gc;}
	return ret * f;
}
#undef gc
const int maxn = 1e5 + 10;
int n;
struct node{
	int l, r;
	bool operator < (const node &a)const{
		return r == a.r ? l < a.l : r < a.r;
	}
}p[maxn];
int w[maxn], L[maxn], R[maxn];
int f[maxn];
int a, b, tot = 0;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	#endif
	n = read();
	for(int i = 1; i <= n; ++i){
		a = read(), b = read();
		// cout<<a<< " "<<b<<endl;
		p[i].l = a + 1, p[i].r = n - b;
	}
	sort(p + 1, p + n + 1);
	for(int i = 1; i <= n; ++i){
		if(p[i].l > p[i].r)continue;
		// cout<<p[i].l<< " "<<p[i].r<<endl;
		if(p[i].l != p[i - 1].l || p[i].r != p[i - 1].r)tot++;
		// cout<<tot<<endl;
		w[tot] = min(w[tot] + 1, p[i].r - p[i].l + 1);
		L[tot] = p[i].l, R[tot] = p[i].r;
	}
	// for(int i = 1; i <= tot; ++i){
	// 	cout<<w[i]<< " "<<L[i]<< " "<<R[i]<<endl;
	// }
	int j = 1;
	for(int i = 1; i <= n; ++i){
		// int j = 1;
		f[i] = f[i - 1];
		// cout<<f[i]<<endl;
		while(j <= tot && R[j] == i){
			// cout<<j<<endl;
			// cout<<L[j]<<endl;
			f[i] = max(f[i], f[L[j] - 1] + w[j]);
			j++;
		}
	}
	printf("%d\n", n - f[n]);
	return 0;
}

CF1016C Vasya And The Mushrooms

题目传送门

题目大意

给定一个$2n$的方格阵，经过一个格子获得的价值为$ai$进入时间,求从左上角出发遍历一次全部格子获得的价值最大值。

大体思路

很明显的一道dp题。。。

稍加思考便能发现能够遍历整个方阵的方案可能是长这样的

或者是长这样的

总之就是先是一个蛇形结构，然后接一个U形结构，很明显这两个部分都是可以预处理的。

设$f[i][0/1]$表示蛇形部分进行到第$i$列，第$0/1$行的权值

则

$\begin{split} &f[i][0]= \begin{cases} \text{f[i-1][0]+(2*(i-1))*val[i][0] (i&1==0)}\\ \text{f[i][1]+(2*(i-1)+1)*val[i][0] (i&1!=0)}\\ \end{cases}\\ &f[i][1]= \begin{cases} \text{f[i][0]+(2*(i-1)+1)*val[i][1] (i&1==0)}\\ \text{f[i-1][1]+(2*(i-1))*val[i][1] (i&1!=0)}\\ \end{cases} \end{split}$

U形部分的计算方法：

$\begin{split} &\text{自左向右的部分}\\ &\sum_{i=k}^n vi*[T+(i-k)]\\ &\downarrow\\ &\sum_{i=k}^n vi*i+\sum_{i=k}^n vi*(T-k)\\ \\ &\text{自右向左的部分}\\ &\sum_{i=k}^n vi*[T+(n-k)+(n-k-i+1)]\\ &\downarrow\\ &\sum_{i=k}^n vi*(T+2*n-2*k+1)-\sum_{i=k}^n vi*i\\ \end{split}$

$k$为U形部分开始的位置

设$g[i][0/1]$表示U形部分从0/1列， i行开始的权值，$sum[i][0/1]$表示本行距离结尾的权值和$nxt[i][0/1]$表示距离结尾的权值与列数乘积之和

则

if(!(i & 1)){
	g[i][1] = nxt[i][1] + (2 * (i - 1) - i) * sum[i][1];
	g[i][1] += (2 * (i - 1) + 2 * n - i + 1) * sum[i][0] - nxt[i][0];
}
else {
	g[i][0] = nxt[i][0] + (2 * (i - 1) - i) * sum[i][0];
	g[i][0] += (2 * (i - 1) + 2 * n - i + 1) * sum[i][1] - nxt[i][1];
}

最后的答案就是每一种合法的蛇形与U形组合取$max$。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long ll;
#define gc ch = getchar()
int read(){
	int ret = 0, f = 1; char gc;
	while(!isdigit(ch) && (ch ^ '-'))gc;
	if(ch == '-')f = -1, gc;
	while(isdigit(ch)){ret = (ret << 3) + (ret << 1) + (ch ^ '0'), gc;}
	return ret * f;
}
ll readll(){
	ll ret = 0, f = 1; char gc;
	while(!isdigit(ch) && (ch ^ '-'))gc;
	if(ch == '-')f = -1, gc;
	while(isdigit(ch)){ret = (ret << 3) + (ret << 1) + (ch ^ '0'), gc;}
	return ret * f;
}
#undef gc
const int maxn = 3 * 1e5 + 10;
int n;
ll ans;
ll val[maxn][2];
ll sum[maxn][2], nxt[maxn][2];
ll f[maxn][2], g[maxn][2];
int main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	#endif
	n = read();
	for(int i = 1; i <= n; ++i){
		val[i][0] = readll();
		// cnt[i][0] = val[i][0] * i;
	}
	for(int i = 1; i <= n; ++i){
		val[i][1] = readll();
		// cnt[i][1] = val[i][1] * i;
	}
	for(int i = n; i >= 1; --i){
		sum[i][0] = sum[i + 1][0] + val[i][0];
		sum[i][1] = sum[i + 1][1] + val[i][1];
		nxt[i][0] = nxt[i + 1][0] + val[i][0] * i;
		nxt[i][1] = nxt[i + 1][1] + val[i][1] * i;
	}
	for(int i = 1; i <= n; ++i){
		if(i & 1){
			f[i][0] = f[i - 1][0] + (2 * (i - 1)) * val[i][0];
			f[i][1] = f[i][0] + (2 * (i - 1) + 1) * val[i][1];
		}
		else{
			f[i][1] = f[i - 1][1] + (2 * (i - 1)) * val[i][1];
			f[i][0] = f[i][1] + (2 * (i - 1) + 1) * val[i][0];
		}
	}
	// for(int i = 1; i <= n; ++i){
	// 	cout<<"sum"<<sum[i][0]<< " "<<sum[i][1]<<endl;
	// 	cout<<"nxt"<<nxt[i][0]<< " "<<nxt[i][1]<<endl;
	// }
	for(int i = 1; i <= n; ++i){
		if(!(i & 1)){
			g[i][1] = nxt[i][1] + (2 * (i - 1) - i) * sum[i][1];
			g[i][1] += (2 * (i - 1) + 2 * n - i + 1) * sum[i][0] - nxt[i][0];
		}
		else {
			g[i][0] = nxt[i][0] + (2 * (i - 1) - i) * sum[i][0];
			g[i][0] += (2 * (i - 1) + 2 * n - i + 1) * sum[i][1] - nxt[i][1];
		}
	}
	// for(int i = 1; i <= n; ++i){
	// 	cout<<"!!"<<f[i][0]<< " "<<f[i][1]<<endl;
	// 	cout<<g[i][0]<< " "<<g[i][1]<<endl;
	// }
	for(int i = 0; i <= n; ++i){
		// cout<<f[i][1]<< " "<<g[i + 1][1]<<endl;
		// cout<<f[i][0]<< " "<<g[i + 1][0]<<endl;
		if(i & 1){
			ans = max(ans, f[i][1] + g[i + 1][1]);
		}
		else {
			ans = max(ans, f[i][0] + g[i + 1][0]);
		}
	}
	cout<<ans<<endl;
	return 0;
}

CF467C George and Job

题目传送门

题目大意

给出一组有$n$个整数的数列$p_1,p_2,…,p_n$，你需要挑出$k$组长度为$m$的数，要求这些数互不重叠，即：$[l_1,r_1],[l_2,r_2],…,l_k,r_k$ 且使选出的数和值最大

大体思路

直接依照题意dp即可。

设$f[i][j]$为当前在第$i$位，选了$j$个区间时的最大值，$s[i]$为以$i$为起始点的长度为$m$的权值之和

转移为：$f[i][j]=max(f[i-1][j],f[i-m][j-1]+s[i])$

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
const int maxn = 5010;
#define gc ch = getchar()
int read(){
	int ret = 0, f = 1;char gc;
	while(!isdigit(ch) && (ch ^ '-'))gc;
	if(!(ch ^'-'))f = -1, gc;
	while(isdigit(ch)){ret = (ret << 3) + (ret << 1) + (ch ^ '0'), gc;}
	return ret * f;
}
long long readll(){
	long long ret = 0, f = 1;char gc;
	while(!isdigit(ch) && (ch ^ '-'))gc;
	if(!(ch ^'-'))f = -1, gc;
	while(isdigit(ch)){ret = (ret << 3) + (ret << 1) + (ch ^ '0'), gc;}
	return ret * f;
}
#undef gc
int n, m, k;
long long p[maxn];
long long f[maxn][maxn];
long long sum[maxn];
long long s[maxn];
int main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	#endif
	n = read(), m = read(), k = read();
	for(int i = 1; i <= n; ++i){
		p[i] = readll();
		sum[i] = sum[i - 1] + p[i];
	}
	for(int i = m; i <= n; ++i){
		s[i] = sum[i] - sum[i - m];
	}
	for(int i = m; i <= n; ++i){
		for(int j = 1; j <= k && j * m <= i; ++j){
			f[i][j] = f[i - 1][j];
			f[i][j] = max(f[i][j], f[i - m][j - 1] + s[i]);
		}
	}
	cout<<f[n][k]<<endl;
	return 0;
}

Just a Blog

2019-7题解综合2——DP

7.29 “简单”DP

luogu P2467 [SDOI2010]地精部落

题目大意

大体思路

代码

luogu P2519 [HAOI2011]problem a

题目大意

大体思路

代码

CF1016C Vasya And The Mushrooms

题目大意

大体思路

代码

CF467C George and Job

题目大意

大体思路

代码

上一页

评论的使用方法

杂项

下一页

2019.7题解综合1 —— 并查集与分治

题解

评论