【dp】砝码称重模型（选或不选）

目录

蓝桥杯 砝码称重

牛客 我不是大富翁 

 abc 344 D

cf div3 933 D 

---

蓝桥杯 砝码称重

题目链接： https://www.lanqiao.cn/problems/1447/learning/?page=1&first_category_id=1&sort=students_count&category_id=3&name=%E7%A0%9D%E7%A0%81%E7%A7%B0%E9%87%8D 

思想:

不选  = j

放右边 = j + a[i]

放左边 = abs (j - a[i])

代码：

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int N = 2e5+5;
 
int n,a[N];
int dp[105][N];
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=1e5;j++){
			if(dp[i-1][j]){
				dp[i][j]=1;  //不选
				dp[i][j+a[i]]=1;  //放右边
				dp[i][abs(j-a[i])]=1;  //放左边
			}
		}
		
	}
	int ans=0;
	for(int i=1;i<=1e5;i++){
		if(dp[n][i]) ans++;
	}
	cout<<ans<<"\n";
	
	
	
	return 0;	
 
}

牛客 我不是大富翁 

题目链接 ：https://ac.nowcoder.com/acm/contest/75771/D

思想：开二维bool 数组，判断第 i 次操作 是否可能位于 j 的位置

代码：

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int N = 5001;
 
int n,m;
int a[N];
bool dp[N][N]; //i次操作是否可能位于j的位置
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		a[i]%=n;
	}
	
	dp[0][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=0;j<n;j++){
			if(dp[i-1][(n+j-a[i])%n]||dp[i-1][(j+a[i])%n]){
				dp[i][j]=1;
			}
			else dp[i][j]=0;
		}
	}
	if(dp[m][0]) cout<<"YES\n";
	else cout<<"NO\n";
	
	
	return 0;	
 
}

 abc 344 D

题目链接：https://atcoder.jp/contests/abc344/tasks/abc344_d

思想：一维数组表示当前长度的最小次数

？为什么要开dp2

代码：

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int N = 1010;
 
string s,t;
int n,m;
int f[N][N];  //表示在前i项中 此时长度为j 的最小次数
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	cin>>s;
	vector<int> dp(s.size()+1,1e15);
	dp[0]=0;
	
	cin>>n;
	for(int i=1;i<=n;i++){
		vector<int> dp2=dp;
		cin>>m;
		while(m--){
			cin>>t;
			for(int j=0;j<s.size();j++){
				if(j+t.size()<=s.size()&&s.substr(j,t.size())==t){
					dp2[j+(int)t.size()]=min(dp2[j+(int)t.size()],dp[j]+1);
				}
			}
		}
		dp=dp2;
	}
	if(dp.back()==1e15){
		cout<<"-1\n";
	}
	else cout<<dp.back()<<"\n";
	
	
	
	return 0;	
 
}
 
 

cf div3 933 D