动态规划各种背包问题刷题

动态规划

两个约束条件

最优子结构：为了计算考虑了前 i 个物品，总体积为 j 时的最大收益，我们可以先计算考虑了前 i - 1 个物品，总体积为 j 时的最大收益以及考虑了前 i - 1 个物品，总体积为 时的最大收益。知道了考虑了前 i - 1 个物品，总体积为 j 时的最大收益以及考虑了前 i - 1 个物品，总体积为 时的最大收益，我们就能算出考虑了前 i 个物品，总体积为 j 时的最大收益。由于在每次拆解过程中我们会少考虑 1 个物品，最后一定会在有限次拆解后变成一个什么物品都不考虑的子问题，所以在问题拆解过程中不会陷入无限递归。

**无后效性：**我们只关心考虑了前 i 个物品，总体积为 j 时的最大收益，不关心具体哪些物品取了，哪些没取

01背包

01背包的意思是每种物品，只有取不取两种选择，每个物品只能选一次

采用二进制枚举每个取或不取，共 2 n 2^n 2n种方案

复杂度 O ( n 2 n ) O(n2^n) O(n2n)

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i  )
        scanf("%d%d", &v[i], &w[i]);
    int ans = 0;
    for (int i = 0; i < 1 << n; i  ) {
        int totv = 0, totw = 0;
        for (int j = 0; j < n; j  )
            if (i & (1 << j))
                totv  = v[j   1], totw  = w[j   1];
        if (totv <= m)
            ans = max(ans, totw);
    }
    printf("%d\n", ans);
}

my reward:二进制枚举是怎么实现的，首先最外层循环控制每个方案，总共有 2 n 2^n 2n种方案嘛，全不选是0，全选是11111，即 2 n − 1 2^n-1 2n−1。然后内层循环是产生$0101001000$这样的二进制数然后一位一位比较过去

dp[N][N]//		第一个参数表示处理到哪个物品，第二个参数表示剩余的容量，整个值表示价值
v[n],w[n]//v表示价值，w表示容量
w// w表示背包的容量
for(int i=1;i<=n;  i){
	for(int j=1;j<=w;  j)
       if(j<w[i]) dp[i][j]=dp[i-1][j];
    else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]] v[i]);
}

往往这样写会MLE，采取优化，用滚动数组来写，即一维数组

for(int i=1;i<=n;  i){
	for(int j=w;j>=w[i];--j){
	dp[j]=max(dp[j],dp[j-w[i]] v[i]);
    }
}
    

完全背包

就是不限次数的取

for(int i=1;i<=n;  i){
	for(int j=w[i];j<=w;  j){
	dp[j]=max(dp[j],dp[j-w[i]] v[i]);
    }
}

多重背包

就是每个物品给了$l[i]$个

可以把他当成01背包来做，显然时间复杂度太大了

所以考虑把他分成1 2 4 8 16…

for(int i=1;i<=n;  i){
    int res=l[i];
    for(int k=1;k<=res;k*=2,res-=k)
        for(int j=m;j>=w[i]*k;j--)
            ans[j]=max(ans[j],ans[j-w[i]*k] v[i]*k);
    for(int j=m;j>=w[i]*res;--j)//最后会剩下个零头，比如res=10  10-1-2-4-3，最后剩个3
        ans[j]=max(ans[j],ans[j-res*w[i]] v[i]*res);
}

分组背包

每组物品只能选一个

vector<int>c[1001];
scanf("%d%d",&n,&m);
for(int i=1;i<=n;  i){
    scanf("%d%d%d",&a[i],&v[i],&w[i]);
    c[a[i]].push_back(i);
}
for(int i=1;i<=1000;  i){
	for(int j=0;j<=m;  j){
        f[i][j]=f[i-1][j];
        for(auto k : c[i])
            if(v[k]<=j)
                f[i][j]=max(f[i][j],f[i-1][j-v[k]] w[k]);
    }
}
	printf("%d",f[1000][m]);

区间dp

1.合并石子问题

有 n 堆石子排成一排，第 i 堆石子有 ai 颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少

#include <bits/stdc  .h>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[510],s[510];
int dp[510][510];//dp[i][j]表示i到j的最小代价 
int main(void) {
int n;
cin>>n;
memset(dp,127,sizeof(dp));
for(int i=1;i<=n;  i) {
	cin>>a[i];
	s[i]=s[i-1] a[i];
}
for(int i=0;i<=n;  i) dp[i][i]=0;//这个初始化不可少哦，因为自己和自己不需要合并
for(int l=1;l<=n-1;  l){
	for(int i=1;i<=n-l;  i){
		int j=i l;
		for(int k=i;k<j;  k){
		dp[i][j]=min(dp[i][j],dp[i][k] dp[k 1][j] s[j]-s[i-1]);
		} 
	}
} 
cout<<dp[1][n];
return 0;
}

因为求的是最小值，所以初始化成inf，这时就要考虑自身与自身不需要合并的情况，是0

石子合并代表了一类涉及到区间的动态规划问题，其核心思想是按长度从小到大的顺序计算每个区间代表的状态的值。解决这类问题的一般思路就是按上面所说的依次枚举区间长度 l、左端点 i 以及分界线位置 k，然后进行状态的更新和转移

2 有 n 堆石子围成一个圈，第 ii 堆石子有 ai 颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少？

#include <bits/stdc  .h>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[510],s[510];
int dp[510][510];//dp[i][j]表示i到j的最小代价 
int main(void) {
int n;
cin>>n;
memset(dp,127,sizeof(dp));
for(int i=1;i<=n;  i) {
	cin>>a[i];
	s[i]=s[i-1] a[i];
	a[i n]=a[i];
}
for(int i=n 1;i<=2*n;  i) s[i]=s[i-1] a[i];
for(int i=0;i<=2*n;  i) dp[i][i]=0; 
for(int l=1;l<2*n;  l){//想不明白为什么是2*n，然后发现n也是对的
	for(int i=1;i<=2*n-l;  i){
		int j=i l;
		for(int k=i;k<j;  k){
		dp[i][j]=min(dp[i][j],dp[i][k] dp[k 1][j] s[j]-s[i-1]);
		} 
	}
} 
int ans=0x3f3f3f3f;
for(int i=1;i<=n-1;  i){
	ans=min(ans,dp[i][i n-1]);
}  
cout<<ans;
return 0;
}

这种把序列倍增（两个相同的序列接起来）的思路在解决很多圆上问题的时候非常有用

直接开两层的数组，好像有圆环的话用这种做法挺多的，比如说1234，就开12341234，即可以满足1234 2341 3412 4123这几种不同的合并方式，然后分别对这些不同的序列求最小值，然后求这n种情况的最小值即可

camp 快快变大

#include <bits/stdc  .h>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long 
int a[400];
int dp[400][400],s[400][400]; 
const int mod=1e6 3;
signed main(void) {
int n;
cin>>n;
for(int i=1;i<=n;  i) {
	cin>>a[i];
	s[i][i]=a[i];
}
    //这里的预处理可能可以通过递推来优化一下
for(int i=1;i<=n;  i){
	for(int j=i 1;j<=n;  j){
		s[i][j]=s[i][j-1]*a[j]%mod;
	}
}
for(int len=1;len<=n;  len){
	for(int i=1;i<=n-len;  i){
		int j=len i;
		for(int k=i;k<j;  k){
			dp[i][j]=max(dp[i][j],dp[i][k] dp[k 1][j] (s[i][k]-s[k 1][j])*(s[i][k]-s[k 1][j]));//考虑最后两堆时，前面合并后的值肯定是前面的乘积（不管合并顺序如何），同理，后一堆也是如此。
		}
	}
}
cout<<dp[1][n];
return 0;
}

要想到不管合并顺序如何，最后的乘积是固定的

也是一道区间dp的题，就是转移后的数会发生变化，所以不会写，建议多看看多理解理解

能量项链

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。

需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4⊕1)=1023=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4⊕1)⊕2)⊕3）=1023 1035 10510=710。

#include<iostream>
using namespace std;

int n,head[201],tail[201],f[201][201];
//f[i][j]为起始为i终点为j的链融合生成的最大能量
//head和tail要拓展数组不然越界要考虑模
//珠子 1 2 3 4 5(1) 6(2) 7(3)
//head 1 3 5 7 1 3 5
//tail 3 5 7 1 3 5 7
//没有再考虑4是因为不需要，枚举不到

void read()
{
    int i,j,k,len,max1;
    cin>>n;
    cin>>head[1];
    for(i=2; i<=n; i  )
    {
        cin>>head[i];

        tail[i-1]=head[i];
    }
    tail[n]=head[1];//读入

    for(i=n 1; i<=2*n-1; i  )
    {
        head[i]=head[i-n];
        tail[i]=tail[i-n];
    }//拓展数组

    for(len=1; len<=n; len  )//枚举链长
        for(i=1; i<=2*n-len; i  )//枚举起始位置
        {
            j=i len;//结束位置

            for(k=i; k<j; k  )//寻找在中间某一位置断开，把两边合并
                f[i][j]=max(f[i][j],f[i][k] f[k 1][j] head[i]*tail[k]*tail[j]);//这里最后三个相乘的要理解一下哦
            //从i到j的最大能量=max(当前能量，从i到k的最大能量 从k 1到j的最大能量
            // 两颗珠子合并释放的能量)
            //注意我们把i到k，k 1到j看做两颗已经合并的珠子，只需把这两颗合并
        }

    max1=0;
    for(i=1; i<=n; i  )
        if(f[i][n i-1]>max1)
            max1=f[i][n i-1];//枚举起始点找最大

    cout<<max1<<endl;

    return;
}

int main()
{
    read();
    return 0;
}

洛谷例题

1. 最大约数和

选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

思路：先把不大于s的约数和算出来，把他当作价值。

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int a[1001];
int dp[1001];
void yue(int n){
	for(int i=2;i<=n;  i){
		for(int j=1;j<i;  j){
			if(i%j==0) a[i] =j;
		}
	}
}
int main(void) {
int n;
cin>>n;
yue(n);
for(int i=1;i<n;  i){
	for(int j=n;j>=i;--j){
		dp[j]=max(dp[j],dp[j-i] a[i]);
	}
}
cout<<dp[n];
return 0;
}

2.1507 NASA的食物计划

每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次.

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=60;
int va[N],wb[N],ans[N];
int dp[410][410];
int main(void) {
int v,w,n;
cin>>v>>w>>n;
for(int i=1;i<=n;  i)
cin>>va[i]>>wb[i]>>ans[i]; 
    //先展示三维空间的做法
//for(int i=1;i<=n;  i){
//	for(int j=0;j<=vmax;  j){
//		for(int k=0;k<=wmax;  k){
//			if(j<v[i]||k<w[i]) dp[i][j][k]=dp[i-1][j][k];
//			else dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-v[i]][k-w[i]] ans[i]);
//		}
//	}
//}
//cout<<dp[n][vmax][wmax];
    
    //二维空间
for(int i=1;i<=n;  i){
	for(int j=v;j>=va[i];--j){
		for(int k=w;k>=wb[i];--k)
		dp[j][k]=max(dp[j][k],dp[j-va[i]][k-wb[i]] ans[i]);
	}
}
cout<<dp[v][w];
return 0;
}

总结：这也是01背包问题，只是多了一个限制条件而已。

1.小A点菜

题意：有m元，n种，接下来是n种菜品的价格，求能到m元有几种方案

dp[0]=1;//这个初始化很important
int n,m;
int w[104];
cin>>n>>m;
for(int i=1;i<=n;  i)
cin>>w[i];
for(int i=1;i<=n;  i){
	for(int j=m;j>=w[i];--j){
		dp[j]=dp[j] dp[j-w[i]];//not max这是关键的地方 
	}
}
cout<<dp[m];
//二维写法
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<=n;  i) dp[i][0]=1;//这里从0开始
	for(int i=1;i<=n;  i) cin>>w[i];
	for(int i=1;i<=n;  i){
		for(int j=1;j<=m;  j){//这里从1开始
//			if(j<w[i]) dp[i][j]=dp[i][j] dp[i-1][j];
//			else dp[i][j]=dp[i][j] dp[i-1][j-w[i]];
			dp[i][j] =dp[i-1][j];
			if(j>=w[i]) dp[i][j] =dp[i-1][j-w[i]];
		}
	}
	cout<<dp[n][m];
}

//用记忆化搜索写的 
#include <bits/stdc  .h>
using namespace std;
typedef long long LL;
LL f[105][10005],n,m,v[105],ans;
LL dfs(LL c,LL k)
{
    if(f[c][k])return f[c][k];
    if(v[c]>k)return 0;
    if(v[c]==k)return 1;
    for(LL i=c 1;i<=n;i  )f[c][k] =dfs(i,k-v[c]);
    return f[c][k];
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(LL i=1;i<=n;i  )scanf("%lld",&v[i]);
    for(LL i=1;i<=n;i  )ans =dfs(i,m);
    printf("%lld\n",ans);
    return 0;
}

2.集合

题意：把1-n的数分成两个集合，使得两个集合的数之和相等，求方案数

//折半 
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
long long dp[800]={1};//初始化很关键 
int main(void) {
int n;
cin>>n; 
int s=(n*(n 1)/2);
if(s%2==1) cout<<0;//为什么这里return 0就可以过了 
else {
	for(int i=1;i<=n;  i){
		for(int j=s/2;j>=i;--j){
			dp[j]=dp[j] dp[j-i];
		}
	}
}
cout<<dp[s/2]/2;
return 0;
}

上述两道动态规划都是关于求方案数的题，初始化显得尤为关键

因为当容量为0时也有一个方案，即什么都不装.

3.精卫填海

//把体力当作体积来算，最后再循环遍历，妙啊 
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001],vi[10001],w[10001];
int main(void) {
int v,n,c;
cin>>v>>n>>c;
for(int i=1;i<=n;  i){
	cin>>vi[i]>>w[i];
} 
for(int i=1;i<=n;  i){
	for(int j=c;j>=w[i];--j){
		dp[j]=max(dp[j],dp[j-w[i]] vi[i]);
	}
}
int flag=0;
for(int i=1;i<=c;  i){
	if(dp[i]>=v) {
		cout<<c-i;
		flag=1;
		break;
	}
}
if(!flag) cout<<"Impossible";
return 0;
}

#include<bits/stdc  .h>
using namespace std;
int k[10005],m[10005],f[10005];
int main()
{
	int v,n,c,i,j;
	scanf("%d%d%d",&v,&n,&c);
	for(i=1;i<=n;i  )
		scanf("%d%d",&k[i],&m[i]);
	memset(f,0x7f,sizeof(f));		//初始化
	f[0]=0;					//填0体积木石所需体力为0
	for(i=1;i<=n;i  )
		for(j=v;j>=1;j--)
			if(j<=k[i]||f[j-k[i]]!=0x7f7f7f7f)	//只填第i块就够，如果不够要保证j-k[i]能填满。否则就填不满j体积
                f[j]=min(f[j],m[i] f[max(0,j-k[i])]);	//max保证下标大于等于0
    if(f[v]<=c)
    	printf("%d",c-f[v]);
    else
    	printf("Impossible");
    return 0;
}

4.神奇的四次方数

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;	
const int N = 1e5   10;
const int inf = 0x3f3f3f3f;
int dp[N];
int w[22];
void solve() {
	fill(dp, dp   N, inf);
	dp[0] = 0;
	for (int i = 1; i <= 18;   i) {
	w[i] = pow(i, 4);
	}
	int n;
	cin >> n;
	for (int i = 1; i <= 18;   i) {
		for (int j = w[i]; j <= n;   j)
			dp[j] = min(dp[j], dp[j - w[i]]   1);
	}
	cout << dp[n];
}
int main() {
	solve();
	return 0;
}

总结：这是一个完全背包的问题，求最小值初始化inf，注意dp[0]=0,若没有这个初始条件，就寄了。并不是所有的dp[0]=1，要具体问题具体分析的

1.最长上升子序列问题

常规做法 动态规划

O ( n 2 ) O(n^2) O(n2)

for(int i=1;i<=n;  i){
	for(int j=1;j<i;  j){
	if(a[i]>a[j])
        dp[i]=max(dp[i],dp[j] 1);
    }
}

贪心 二分

O ( n l o g n ) O(nlog_n) O(nlogn)

#include<iostream>
using namespace std;
// 使用二分法的前提是 数组是已经排好序的（刚好在这里我们的d数组就是递增数组）
//d数组记录的是长度为i的最小的末尾值，末尾越小，成为上升子序列的潜力越大，这就是贪心的思想，d[2]表示长度为2的序列中的末尾的最小值
// 查找返回d数组中第一个比x大的值的下标
int er_method(int a[],int len,int x)
{
    int mid,l=1;
    while(l<=len)
    {
        mid = (l len)/2;
        if(a[mid]<=x)
            l = mid 1;
        else
            len = mid-1;
    }
    return l;// 此时mid等于l
}
int main()
{
    int n;
    while(cin>>n)
    {
        //待测的数组-------    a
        //存放最长子序列---     d
        //记录最长子序列的长度-- len
        int a[101],d[101],len=1;
        for(int i=1;i<=n;i  )
        {
            cin>>a[i];
        }
        d[1]=a[1];   // 第一个待测数字就d的第一个
        if(n<2)  // 如果待测数字只有一个 ，那就这个数字就是最长子序列
        {
            cout<<1<<endl;
            continue;
        }
        for(int i=2;i<=n;i  )
        {
            if(a[i]>d[len]) // 如果第 i个数大于d数组的最大的数，直接接在d数组的后面
                d[  len] = a[i];
            else    // 比d数组的最大数值小的的话，那就在d数组中找到一个比它大的数，替换掉
                d[er_method(a,len,a[i]] = a[i]; // 这一步不改变d 数组的长度
        }
        cout<<len<<endl;
    }
    return 0;
}

2.最长公共子序列

常规做法 动态规划

O ( n 2 ) O(n^2) O(n2)

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5 10;
int a[N],b[N],dp[1000][1000];
int main(void) {
int n;
cin>>n;
for(int i=1;i<=n;  i) cin>>a[i];
 for(int i=1;i<=n;  i) cin>>b[i];
 for(int i=1;i<=n;  i){
 	for(int j=1;j<=n;  j){
 		if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1] 1;
 		else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//这是为什么呢
	 }
 }
 cout<<dp[n][n];
return 0;
}

第二种做法

O ( n l o g n ) O(nlog_n) O(nlogn)

#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5   10;
int a1[N], a2[N], belong[N];
int b[N], f[N];
int main(void) {
    int n;
    scanf("%d", &n);
    int len = 0;
    for (int i = 1; i <= n; i  )
    {
        scanf("%d", &a1[i]);
        belong[a1[i]] = i;
    }
    for (int i = 1; i <= n; i  )
        scanf("%d", &a2[i]);
    for (int i = 1; i <= n; i  )
    {
        if (belong[a2[i]] > b[len])
        {
            b[  len] = belong[a2[i]];
            f[i] = len;
            continue;
        }
        int k = lower_bound(b   1, b   len   1, belong[a2[i]]) - b;
        b[k] = belong[a2[i]];
        f[i] = k;
    }
    printf("%d\n", len);
}

关于为什么可以转化成LIS问题（最长上升子序列），这里提供一个解释。

A:3 2 1 4 5

B:1 2 3 4 5

我们不妨给它们重新标个号：把3标成a,把2标成b，把1标成c……于是变成：

A: a b c d e
B: c b a d e

这样标号之后，LCS长度显然不会改变。但是出现了一个性质：

两个序列的子序列，一定是A的子序列。而A本身就是单调递增的。
因此这个子序列是单调递增的。

换句话说，只要这个子序列在B中单调递增，它就是A的子序列。

哪个最长呢？当然是B的LIS最长。

自此完成转化。

camp

day2

楼梯有 n阶，上楼可以一步上一阶，也可以一步上二阶。

但你不能连续三步都走两阶，计算走到第n阶共有多少种不同的走法。

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
long long int dp[110][3];
void solve(){
	int n;
	long long sum=0;
	cin>>n;
	dp[1][0]=1;
	dp[2][1]=1;
	dp[2][0]=1;
	for(int i=3;i<=n;  i){
		for(int j=0;j<3;  j)
		dp[i][0]=dp[i][0] dp[i-1][j];
		dp[i][1]=dp[i][1] dp[i-2][0];
		dp[i][2]=dp[i][2] dp[i-2][1];
	}
	for(int i=0;i<3;  i) sum =dp[n][i];
	cout<<sum; 
}
int main(void) {
//int n;
//dp[0]=1;
//dp[1]=1;
//cin>>n;
//for(int i=2;i<=n;  i){
//	dp[i]=dp[i-1] dp[i-2];
//	if(i>6) dp[i]=dp[i]-dp[i-7];
//	if(i==6) dp[i]--;
//}
//cout<<dp[n];
solve();
return 0;
}

my reward:

1.找规律其实挺难找的，找了n年

2.$dp[i][j]$表示走到第i层时连续跳两层了j次 则$dp[i][0]=dp[i-1][0]dp[i-1][1]dp[i-1][2]$ 因为是连续的嘛，所以从上一层跳过来只能跳一层，所以j肯定变为0了。

day3

有一条很长的数轴，一开始你在00的位置。接下来你要走n步，第i步你可以往右走ai或者bi。

问n步之后，0到m的每个位置，能不能走到？

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5 5;
int f[110][N];
int a[110],b[110]; 
int main(void) {
int n,m;
f[0][0]=1;
cin>>n>>m;
for(int i=1;i<=n;  i){
	cin>>a[i]>>b[i];
}
for(int i=1;i<=n;  i){
	for(int j=1;j<=m;  j){
		if(j>=a[i]){
			if(f[i-1][j-a[i]]) f[i][j]=1;
		}
		if(j>=b[i]){
			if(f[i-1][j-b[i]]) f[i][j]=1;
		}
	}
}
for(int i=0;i<=m;  i){
	if(f[n][i]) cout<<1;
	else cout<<0;
}
return 0;
}

my reward: $f[i][j]$表示第几步能否走到j，若为1表示能走到，想到其实也挺easy的

一维的怎么写

for(int i=1;i<=n;  i){
	for(int j=m;j>=0;--j){
		int flag=0;
		if(j>=a[i]){
			if(f[j-a[i]]) {
				f[j]=1;
				flag=1;
			}
			else f[j]=0;
		}
		if(j>=b[i]&&flag==0){
			if(f[j-b[i]]) f[j]=1;
			else f[j]=0;
		}
		if(j<a[i]&&j<b[i]) f[j]=0;	
	}
	if(i==1) f[0]=0;
}
for(int i=0;i<=m;  i){
	if(f[i]) cout<<1;
	else cout<<0;

reward：刚开始不开flag，就寄了，因为假如你满足了a，f[j]变成了1，但是你不满足b，f[j]就变回0了

训练赛

#include <bits/stdc  .h>
#define ll long long
using namespace std;
const int N = 1e9   7;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s1, s2;
    while (cin >> s1 >> s2) {
        ll i, j, h, a[1001], max = 0;
        for (i = 0; i < s2.size(); i  )a[i] = 0;
        for (i = 0; i < s1.size(); i  ) {
            for (j = s2.size() - 1; j >= 0; j--) {
                if (s1[i] == s2[j]) {
                    if (j != 0) a[j]  = a[j - 1];
                    else a[j]  ;
                    a[j] %= N;
                }
            }
        }
        cout << a[s2.size() - 1] << endl;
    }
    return 0;
}

题目大意

给定n,m,p,q,从（1，1）走到（n,m），只能向右或者向下走，每个点都是0或1，要你求走到右下角的方案数（满足0至少有p，1至少有q）

#include <bits/stdc  .h>
using namespace std;
const int mod=998244353;
int dp[2][510][10001];//第三维记录0的个数
int a[510][510];
int n,m,p,q;
init(){
	cin>>n>>m>>p>>q;
	for(int i=1;i<=n;  i){
		for(int j=1;j<=m;  j){
			cin>>a[i][j];
		}
	}
	dp[1][1][a[1][1]==0]=1;//初始化
}
int main(void){
	int sum=0;
	init();
	for(int i=1;i<=n;  i){
		for(int j=1;j<=m;  j){
			if(i==1&&j==1) continue;
			for(int k=0;k<=i j-1;  k){
				if(a[i][j]==1) dp[i%2][j][k]=dp[(i-1)%2][j][k] dp[i%2][j-1][k];
				else 
				{
					if(k==0) dp[i%2][j][0]=0;
					else dp[i%2][j][k]=dp[i%2][j-1][k-1] dp[(i-1)%2][j][k-1];	
				}
				dp[i%2][j][k]=dp[i%2][j][k]%mod;
			}
		}
	}
	for(int k=p;k<=n m-1-q;  k){
		sum=(sum dp[n%2][m][k])%mod;
	}
	cout<<sum%mod;
	return 0;
}

其实转移方程还是挺好想的，但是会爆内存，于是考虑把第一维降下来，只有0或者1

牛客竞赛网

被3整除的子序列

给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除
答案对1e9 7取模

#include <bits/stdc  .h>
using namespace std;
int dp[60][3];
const int mod=1e9 7;
#define int long long 
signed main(void){
    string str;
     getline(cin,str);
    int len=str.size();
    if((str[0]-'0')%3==0) dp[0][0]=1;
    else if((str[0]-'0')%3==1) dp[0][1]=1;
    else if((str[0]-'0')%3==2) dp[0][2]=1;
    for(int i=1;i<len;  i){
            if((str[i]-'0')%3==0) {
                dp[i][0]  ;
            dp[i][0]=(dp[i][0] dp[i-1][0] dp[i-1][0])%mod;
            dp[i][1]=(dp[i][1] dp[i-1][1] dp[i-1][1])%mod;
            dp[i][2]=(dp[i][2] dp[i-1][2] dp[i-1][2])%mod;
        }
           else if((str[i]-'0')%3==1){
               dp[i][1]  ;
            dp[i][0]=(dp[i][0] dp[i-1][0] dp[i-1][2])%mod;
            dp[i][1]=(dp[i][1] dp[i-1][1] dp[i-1][0])%mod;
            dp[i][2]=(dp[i][2] dp[i-1][2] dp[i-1][1])%mod;
           }
            else if((str[i]-'0')%3==2){
                dp[i][2]  ;
            dp[i][0]=(dp[i][0] dp[i-1][0] dp[i-1][1])%mod;
            dp[i][1]=(dp[i][1] dp[i-1][1] dp[i-1][2])%mod;
            dp[i][2]=(dp[i][2] dp[i-1][2] dp[i-1][0])%mod;
       }
    }
    cout<<dp[len-1][0];
    return 0;
}
//dp[i][j]表示前i个余数为j的有几个，那么到第i个，有两种选择，若选i，那么加上dp[i-1][.....],如果不选，那么加上dp[i-1][j]

//稍加优化的版本，就是用一个for循环来代替分类讨论吗
#include <bits/stdc  .h>
using namespace std;
int dp[60][3];
const int mod=1e9 7;
#define int long long 
signed main(void){
    string str;
     getline(cin,str);
    int len=str.size();
    if((str[0]-'0')%3==0) dp[0][0]=1;
    else if((str[0]-'0')%3==1) dp[0][1]=1;
    else if((str[0]-'0')%3==2) dp[0][2]=1;
    for(int i=1;i<len;  i){
          int m=(str[i]-'0')%3;
        dp[i][m]  ;
        for(int j=0;j<3;  j){
            dp[i][j]=(dp[i][j] dp[i-1][j] dp[i-1][(j 3-m)%3])%mod;
        }
    }
    cout<<dp[len-1][0];
    return 0;
}

这篇好文章是转载于：学新通技术网