dp刷题练习
题目来源：洛谷题单 新手动态规划合集
给定一个正整数n，求将其分解成若干素数之和的方案总数
solution：先欧拉筛打出素数表，然后跑一遍完全背包即可
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1005;
int n,f[maxn],prime[maxn],phi[maxn],cnt;
inline void init(int n){
phi[1]=1;
f[0]=f[1]=1;
for(int i=2;i<=n;i++){
if(f[i]==0){
prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
f[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}else phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
ll dp[maxn];
int main() {
scanf("%d",&n);
init(n);
dp[0]=1;
for(int i=1;i<=cnt;i++){
for(int j=0;j<=n;j++){
if(j>=prime[i]) dp[j]+=dp[j-prime[i]];
}
}
printf("%lld\n",dp[n]);
return 0;
}
|
给一个字符串集合，和一个长字符串，问能用集合中的元素拼成长字符串的最长前缀长度是多少
solution：对于集合中的每个字符串，我们可以先跑一遍KMP的到next数组，然后去匹配长字符串，如果可以匹配上，就用一个前缀和数组将对应位置打上标记（+1），最后求一遍前缀和，过程中如果出现等于0的和，说明这一位没有匹配到，那么最长前缀就是这一位之前的所有字符的个数
(这是dp嘛。。)
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<bits/stdc++.h>
using namespace std;
string s,t[205];
int kmp[205],sum[200005];
int main() {
int cnt=1;
while(cin>>t[cnt]){
if(t[cnt]=="."){
cnt--;
break;
}
t[cnt]="0"+t[cnt];
cnt++;
}
string temp;
s+="0";
while(cin>>temp){
s+=temp;
}
int len=s.size();
for(int k=1;k<=cnt;k++){
memset(kmp,0,sizeof(kmp));
int j=0;
for(int i=2;i<=t[k].size();i++){
while(j&&t[k][j+1]!=t[k][i]) j=kmp[j];
if(t[k][j+1]==t[k][i]) j++;
kmp[i]=j;
}
j=0;
for(int i=1;i<=len;i++){
while(j&&t[k][j+1]!=s[i]) j=kmp[j];
if(t[k][j+1]==s[i]) j++;
if(j==t[k].size()-1){
sum[i-t[k].size()+2]++;
sum[i+1]--;
j=kmp[j];
}
}
}
for(int i=1;i<=len;i++){
sum[i]+=sum[i-1];
if(sum[i]<=0){
cout<<i-1<<endl;
return 0;
}
}
cout<<len<<endl;
return 0;
}
|
给出一段序列代表零食的价值，每天只可以取出头部或者尾部的一个零食，每次卖出的价格为天数x价值，求卖出去的最大总价格
solution：区间dp，定义状态如下
初始化时，dp[i][i]=n*v[i]，因为如果只剩下物品，那么最后一天卖是最赚的，除此之外，每次更新时，都需要将卖出的新物品置为倒数第len个卖的（len为区间长度），其实如果要方便理解的话，可以倒着枚举长度
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const int inf=2147483647;
const int maxn = 10000;
int n,a[2005];
int dp[2005][2005];
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++) dp[i][i]=a[i]*n;
for(int len=2;len<=n;len++){
for(int j=1,ends=j+len-1;ends<=n;j++,ends=j+len-1){
dp[j][ends]=max(dp[j+1][ends]+a[j]*(n-len+1),dp[j][ends-1]+a[ends]*(n-len+1));
}
}
printf("%d\n",dp[1][n]);
return 0;
}
|
给一段序列，问要使得序列严格先升后降，最少需要删除几个元素
solution：从左往右跑一遍LIS，再从右往左跑一遍LIS，最后枚举每个元素，计算dp1[i]+dp2[i]-1的最大值，拿序列长度减去这个最大值就是答案
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include<bits/stdc++.h>
using namespace std;
int dp1[105],dp2[105],a[105];
int ans;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
dp1[i]=1;
for(int j=1;j<=n;j++){
if(a[i]>a[j]) dp1[i] = max(dp1[i],dp1[j]+1);
}
}
for(int i=n;i>=1;i--){
dp2[i]=1;
for(int j=n;j>=1;j--){
if(a[i]>a[j]) dp2[i] = max(dp2[i],dp2[j]+1);
}
}
for(int i=1;i<=n;i++){
ans = max(ans,dp1[i]+dp2[i]-1);
}
cout<<n-ans<<endl;
return 0;
}
|
有n种花，每种花a[i]盆，要求摆m盆，同种花需要连续摆，问有多少种摆法
solution：dp，定义状态如下
初始化dp[0][0]=1
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int mod=1e6+7;
int n,m,a[105];
int dp[105][105];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=min(j,a[i]);k++){
dp[i][j]=(dp[i][j]+dp[i-1][j-k])%mod;
}
}
}
printf("%d\n",dp[n][m]);
return 0;
}
|
一个人要逃离荒岛，在1s内他可以选择跑步（17m/s，不耗蓝）、闪现（60m/s 耗10点蓝）、原地休息（回蓝4点/s），给出初始法力值、离出口的距离、荒岛沉默的时间，问能否逃出，如果能，输出最短时间，否则输出能逃的最远距离
solution：将闪现和跑步分开处理，先处理闪现，在规定时间内，能交闪现就交，否则就原地回蓝，dp一遍处理好之后，再处理跑步
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int m,s,t;
int dp[300005];
int main(){
scanf("%d%d%d",&m,&s,&t);
for(int i=1;i<=t;i++){
if(m>=10) m-=10,dp[i]=dp[i-1]+60;
else m+=4,dp[i]=dp[i-1];
}
for(int i=1;i<=t;i++){
dp[i]=max(dp[i-1]+17,dp[i]);
if(dp[i]>=s){
printf("Yes\n%d\n",i);
return 0;
}
}
printf("No\n%d\n",dp[t]);
return 0;
}
|
给一个字符串，问能使其回文所需插入的最少字符数
solution：原字符串和自身reverse的LCS长度就是不需要改变的长度，所以剩下的就是需要插入的字符个数
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
string s,t;
int dp[1005][1005];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>s;
t=s;
reverse(t.begin(),t.end());
int lens=s.size(),lent=t.size();
for(int i=0;i<lens;i++){
for(int j=0;j<lent;j++){
if(s[i]==t[j]){
dp[i+1][j+1]=dp[i][j]+1;
}else{
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
}
}
}
cout<<lens-dp[lens][lent]<<endl;
return 0;
}
|
有N种纪念品，有T天可以交易，初始有M块钱，给出每种纪念品在每天的价格，每天可以任意次地购买或卖出任意纪念品（前提是手上的钱足够），问最后手里能最多有多少钱
solution：需要巧妙地转换一下，如果我们在第i天买了一个东西，而在第i+1天卖掉它，再立刻买它的话，就相当于在第i+1天没有对这个东西做任何交易，因此这样就可以把连续的不交易转换成每天都进行一次无效的（或有效的）交易，因此可以将两天的物品价格做一个差分，这个差值就是两天交易的收益（可以是负的），而代价是前一天的价格，因此问题转换成了背包，但是，这个背包多了一层维度，就是天数，因此需要先枚举每一天，在每一天对所有种类的物品做一次背包，得出最大的收益，然后更新最大收益，到下一天，如此循环到倒数第二天（因为倒数第一天买卖无意义了），注意每次都要给dp数组置零，以及更新最大收益
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const int inf=2147483647;
const int maxn = 10000;
int t,n,m,p[105][105];
int dp[10005];
int main() {
scanf("%d%d%d",&t,&n,&m);
for(int i=1;i<=t;i++){
for(int j=1;j<=n;j++){
scanf("%d",&p[i][j]);
}
}
for(int i=1;i<t;i++){
memset(dp,0,sizeof(dp));
for(int j=1;j<=n;j++){
for(int k=p[i][j];k<=m;k++){
dp[k]=max(dp[k],dp[k-p[i][j]]+p[i+1][j]-p[i][j]);
}
}
m=max(m,dp[m]+m);
}
printf("%d\n",m);
return 0;
}
|
一个机房有两位神犇，有n个同学，他们都会膜拜两位中的一位，现在要给同学们分机房，老师只会把连续一段的同学分进一个机房，需要保证每个机房的两位神犇的崇拜者人数之差不超过m，问至少需要多少个机房
solution：定义状态如下
考虑如何转移，如果中间有一段同学都是膜拜同一个神犇的，则就把他们都分配到一个机房就行了，比较巧妙的是，可以在初始输入时利用前缀和处理，膜拜其中一个神犇的就+1，另一个的就-1，那么转移方程如下
即：如果有一段同学都是膜拜同一个神犇的，或者两者差值不超过m，则可以转移，就是把这一段同学分配到一个同一个房间中
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const int inf=2147483647;
const int maxn = 10000;
int n,m,a[2505],sum[2505];
int dp[2505];
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
if(x==2) a[i]=a[i-1]-1;
else a[i]=a[i-1]+1;
dp[i]=1e9;
}
dp[1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(abs(a[i]-a[j-1])==i-j+1||abs(a[i]-a[j-1])<=m){
dp[i]=min(dp[i],dp[j-1]+1);
}
}
}
printf("%d\n",dp[n]);
return 0;
}
|
给出一串序列代表依次发射过来的导弹高度，每个拦截系统只能拦截不超过前一次拦截的导弹高度的导弹，问最多能拦截多少导弹，以及如果要拦截所有导弹，需要多少导弹拦截系统
solution：第一问很简单，就是求一个最长不上升子序列（upper_bound可以解决），第二问需要转化一下，可以草稿纸上画画图，其实就是求最长上升子序列的长度
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const int inf=2147483647;
const int maxn = 100105;
int a[maxn],n;
int dp2[maxn],dp1[maxn],len1,len2;
int main() {
int x;
while(cin>>x){
a[++n]=x;
}
for(int i=1;i<=n;i++){
if(dp2[len2]<a[i]) dp2[++len2]=a[i];
else{
int pos=lower_bound(dp2+1,dp2+1+len2,a[i])-dp2;
dp2[pos]=a[i];
}
if(len1==0||dp1[len1]>=a[i]) dp1[++len1]=a[i];
else{
int pos=upper_bound(dp1+1,dp1+1+len1,a[i],greater<int>())-dp1;
dp1[pos]=a[i];
}
}
printf("%d\n%d\n",len1,len2);
return 0;
}
|
有n本书，问从中去掉m本后所有书的不整齐度最小是多少（不整齐度定义为每两本书的宽度的差的绝对值的和）
solution：转换一下，及时求从n本书中选出n-m本书，使得不整齐度最小，则可以定义状态如下
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m;
struct node{
int x,y;
}a[205];
bool cmp(node x1,node x2){
return x1.x<x2.x;
}
int cha,dp[205][205];
int main(){
scanf("%d%d",&n,&m);
m=n-m;
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
}
memset(dp,1,sizeof(dp));
for(int i=1;i<=n;i++) dp[i][1]=0;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
for(int j=1;j<=min(i,m);j++){
for(int k=1;k<i;k++){
dp[i][j]=min(dp[i][j],dp[k][j-1]+abs(a[i].y-a[k].y));
}
}
}
int ans=1e9;
for(int i=1;i<=n;i++){
ans=min(ans,dp[i][m]);
}
printf("%d\n",ans);
return 0;
}
|
有n棵樱花树，有的樱花树能无限次看，有的有限定次数，每个樱花看一次需要花费指定的时间，因此可以得到指定的美学值，问在时间范围内可以获得的最大美学值是多少
solution：一眼就看出是完全背包+分组背包的混合，直接写就行
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const int inf=2147483647;
const int maxn = 10015;
int a1,a2,b1,b2,n,a[maxn],b[maxn],p[maxn];
int dp[maxn/10];
int main() {
scanf("%d:%d %d:%d %d",&a1,&b1,&a2,&b2,&n);
if(a2<a1) a2+=24;
int ti=(a2-a1)*60+(b2-b1);
for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&p[i]);
for(int i=1;i<=n;i++){
if(p[i]==0){
for(int j=a[i];j<=ti;j++){
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
}else{
for(int j=ti;j>=0;j--){
for(int k=1;k<=p[i];k++){
if(j>=k*a[i]) dp[j]=max(dp[j],dp[j-k*a[i]]+k*b[i]);
}
}
}
}
printf("%d\n",dp[ti]);
return 0;
}
|
翻译过来就是：给一个n*m的矩阵，问从左上角走到右下角（矩阵元素值都为0），走两条完全不同的路，所获得的最大收益（收益为经过的矩阵元素之和）
solution：由于是同步走，所以突破点就在于任何时刻的步数是一样的，只不过所在的坐标位不一样，因而只需要知道了横纵坐标中的任意一个值，就是可得到另一个值，于是定义如下状态
那么转移如下：
但是由于两者不能走同一个格子，所以当i==j时，就是重合的时候，这种情况下，转移的时候只能加一次矩阵元素值，因此上面的更新可以分开来写，加元素值的时候，写成下面的样子
dp[sum][i][j]+=(i==j)?mm[i][sum-i+1]:mm[i][sum-i+1]+mm[j][sum-j+1]
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const int inf=2147483647;
const int maxn=10000;
const int mod=1e9+7;
int n,m,mm[55][55];
int dp[250][55][55];
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&mm[i][j]);
}
for(int sum=2;sum<=n+m-1;sum++){
for(int i=1;i<=n&&i<=sum;i++){
for(int j=1;j<=n&&j<=sum;j++){
dp[sum][i][j]=max(max(dp[sum-1][i-1][j],dp[sum-1][i][j-1]),max(dp[sum-1][i][j],dp[sum-1][i-1][j-1]));
dp[sum][i][j]+=(i==j)?mm[i][sum-i+1]:(mm[i][sum-i+1]+mm[j][sum-j+1]);
}
}
}
printf("%d\n",dp[n+m-1][n][n]);
return 0;
}
|
有一个n*m的矩阵，每次从每一行的左右两端任取一个元素出来，得到对应的得分（乘以$2^i$，$i$表示第$i$次取），问最终能获得的得分最大值
solution：任意行与行之间的取数是相互独立的，因此考虑对每一行进行区间dp，对于第$i$行，定义状态$dp[st][en]$：取到剩下$st$位置到$en$位置时，这一行所对应的的得分最大值，则转移方程如下：
即：从区间左端点左侧转移过来或者从右端点右侧转移过来，最后需要在所有的$dp[j][j]$中找$dp[j][j]+2^m$的最大值更新答案，对于每一行都如此操作，最后求和就是答案
PS：需用高精，然而__int128也可过
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<bits/stdc++.h>
typedef long long ll;
using namespace std;
template<class T> void read(T &x) {
x=0;int f=0;char ch=getchar();
while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return;
}
inline void write(__int128 x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
__int128 n,m,a[85][85],dp[85][85];
inline __int128 qpow(__int128 x,__int128 y){
__int128 base=x,ans=1;
while(y){
if(y&1) ans*=base;
base*=base;
y>>=1;
}
return ans;
}
int main(){
read(n),read(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
read(a[i][j]);
}
}
__int128 ans=0;
for(int i=1;i<=n;i++){
memset(dp,0,sizeof(dp));
for(int len=m;len>=1;len--){
for(int st=1,en=st+len-1;en<=m;st++,en=st+len-1){
dp[st][en]=max(dp[st][en],max(dp[st-1][en]+a[i][st-1]*qpow(2,m-(en-st+1)),dp[st][en+1]+a[i][en+1]*qpow(2,m-(en-st+1))));
}
}
__int128 tp=-1;
for(int j=1;j<=m;j++){
tp=max(tp,qpow(2,m)*a[i][j]+dp[j][j]);
}
ans+=tp;
}
write(ans);
putchar('\n');
return 0;
}
|
给出一棵有边权的二叉树，要求保留从根节点出发的q条边，删去其余边，问剩余的树的边权和最大值
solution：树形dp，考虑第$u$号节点，定义状态$dp[u][j]$：以$u$节点为根的子树保留$j$条边所具有的的最大边权和，则转移方程如下：
其中，$v$为一个子节点，$edge.w$为$u,v$的边权，$k$代表$v$这棵子树保留$k$条边，且 $j\le \min(size[u],q),k<=\min(size[v],q)$，其中$size$为子树大小
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<bits/stdc++.h>
typedef long long ll;
using namespace std;
template<class T> void read(T &x) {
x=0;int f=0;char ch=getchar();
while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return;
}
int n,q;
struct Edge
{
int u,v,w,next;
}e[205];
int cnt,head[205],dp[205][205],sz[205];
inline void addedge(int u,int v,int w){e[cnt]={u,v,w,head[u]},head[u]=cnt++;}
void dfs(int u,int fath){
for(int i=head[u];~i;i=e[i].next){
int v=e[i].v;
if(v!=fath){
dfs(v,u);
sz[u]+=sz[v]+1;
}
}
for(int i=head[u];~i;i=e[i].next){
int v=e[i].v,w=e[i].w;
if(v!=fath){
for(int j=min(q,sz[u]);j>=0;j--){
for(int k=min(j-1,q);k>=0;k--){
dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[v][k]+w);
}
}
}
}
}
int main(){
read(n),read(q);
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++){
int u,v,w;
read(u),read(v),read(w);
addedge(u,v,w),addedge(v,u,w);
}
dfs(1,-1);
printf("%d\n",dp[1][q]);
return 0;
}
|