蓝桥杯训练 | 数学和简单DP | 03

目录

• 买不到的数目
• 蚂蚁感冒
• 饮料换购
• 01背包问题
• 摘花生
• 最长上升子序列
• 地宫取宝
• 波动数列

买不到的数目

暴力做法

#include<bits/stdc++.h>
using namespace std;

int n,m;

bool check(int x){
    for(int i=0;i<=x/n;i++){
        for(int j=0;j<=x/m;j++){
            int t=i*n+j*m;
            if(t==x)return true;
        }
    }
    return false;
}

int main(){
    cin >> n >> m;
    int res=0;
    for(int i=0;i<=n*m;i++){
        if(!check(i))res=i;
    }
    cout << res << endl;
    return 0;
}

结论公式

#include<iostream>
using namespace std;


int main(){
	int a,b;
	cin >> a >> b;
	cout << a*b - a - b << endl;
	
	return 0;
} 

蚂蚁感冒

#include<bits/stdc++.h>
using namespace std;

const int N=55;
int q[N];
int n;

/*
1) |-> <-| <-
2) -> |-> <-|
*/
int cmp(int a,int b){
	return abs(a)<abs(b);
}

int main(){
	cin >> n;
	for(int i=0;i<n;i++)scanf("%d",&q[i]);
	int x=q[0];
	sort(q,q+n,cmp);
	int k=0;
	while(q[k]!=x)k++;
	int res=0,l=0,r=0;
	if(x>0){
		for(int i=k+1;i<n;i++)
			if(q[i]<0)r++;
		if(r==0){
			cout << 1 << endl;
			return 0;
		}else{
			for(int i=0;i<k;i++)
				if(q[i]>0)l++;
			cout << l + r + 1 << endl;
		}
	}else{
		for(int i=0;i<k;i++)
			if(q[i]>0)l++;
		if(l==0){
			cout << 1 << endl;
			return 0;
		}else{
			for(int i=k+1;i<n;i++)
				if(q[i]<0)r++;
			cout << l + r + 1 << endl;
		}
	}
	
	return 0;
} 

饮料换购

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,m; // 瓶子,瓶盖 
	cin >> n;
	m = n;
	while(m>2){
		m-=3;
		n+=1;
		m+=1;
	}
	cout << n << endl;
	return 0;
} 

01背包问题

朴素做法

#include<bits/stdc++.h>
using namespace std;

const int N=1010;
int f[N][N];
int w[N],v[N];


int main(){
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout << f[n][m] << endl;
    
    return 0;
}

空间优化

#include<bits/stdc++.h>
using namespace std;

const int N=1010;
int f[N];
int w[N],v[N];


int main(){
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout << f[m] << endl;
    
    return 0;
}

摘花生

#include<bits/stdc++.h>
using namespace std;

const int N=110;
int f[N][N],w[N][N];


int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%d",&w[i][j]);
			}
		}
		
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
			}
		}
		cout << f[n][m] << endl;
	}
	
	return 0;
} 

最长上升子序列

#include<bits/stdc++.h>
using namespace std;

const int N=1000+10;
int w[N],f[N];


int main(){
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	for(int i=1;i<=n;i++){
		f[i]=1;
		for(int j=1;j<i;j++){
			if(w[j]<w[i])f[i]=max(f[j]+1,f[i]);
		}
	}
	int res=0;
	for(int i=1;i<=n;i++)res=max(res,f[i]);
	cout << res << endl;
	return 0;
} 

地宫取宝

#include<bits/stdc++.h>
using namespace std;

const int N=55,MOD=1e9+7;
int f[N][N][13][14],w[N][N];

int main(){
	int n,m,k;
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> w[i][j];
			w[i][j]++;
		}
	}
	// 初始化 
	f[1][1][1][w[1][1]]=1; // 取
	f[1][1][0][0]=1; // 不取
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i==1&&j==1)continue;
			for(int cnt=0;cnt<=12;cnt++){
				for(int c=0;c<=13;c++){
					// 不取
					f[i][j][cnt][c]=(f[i][j][cnt][c]%MOD+f[i-1][j][cnt][c]%MOD)%MOD; 
					f[i][j][cnt][c]=(f[i][j][cnt][c]%MOD+f[i][j-1][cnt][c]%MOD)%MOD; 
					// 取
					if(cnt>0 && c==w[i][j]){
						for(int s=0;s<c;s++){
							f[i][j][cnt][c]=(f[i][j][cnt][c]%MOD+f[i-1][j][cnt-1][s]%MOD)%MOD; 
							f[i][j][cnt][c]=(f[i][j][cnt][c]%MOD+f[i][j-1][cnt-1][s]%MOD)%MOD; 
						}
					} 
				}
			}
		}
	} 
	int res=0;
	for(int i=0;i<=13;i++)res = (res%MOD+f[n][m][k][i]%MOD)%MOD;
	cout << res << endl;
	return 0;
} 

波动数列

#include<bits/stdc++.h>
using namespace std;

const int N=1010,MOD=1e8+7;
int f[N][N];

int get_mod(int a,int b){
	return (a%b+b)%b;
}

int main(){
	int n,s,a,b;
	cin >> n >> s >> a >> b;
	f[0][0]=1; // 方案数的初始化 
	for(int i=1;i<n;i++){
		for(int j=0;j<n;j++){
			f[i][j] = (f[i][j]%MOD + f[i-1][get_mod(j-(n-i)*a,n)]%MOD)%MOD;
			f[i][j] = (f[i][j]%MOD + f[i-1][get_mod(j+(n-i)*b,n)]%MOD)%MOD;
		}
	}
	
	cout << f[n-1][get_mod(s,n)] << endl;
	return 0; 
}