题目：

代码：

#include <iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	double p = 5*(n-32)/9;
	printf("Celsius = %d",(int)p);
	return 0;
}

T2 查验身份证（模拟）

题目：

样例：

数学不好，题都要读不懂了（什么是权重啊呜呜）

代码：

#include <iostream>
using namespace std;
const int mod = 11;
string a;
char m[11]={'1','0','X','9','8','7','6','5','4','3','2'};
int q[19]={0,7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
bool check(int z,char c){
	if(m[z]!=c)	return false;
	return true;
}
int main(){
	bool all=true;
	int t=1; cin>>t;
	int n = t;
	while(t--){
		cin>>a;
		int sum=0,zz;
		bool single = true;
		for(int i=0;i<17;i++){
			if(a[i]<'0'||a[i]>'9'){
				all = false;
				single = false;
			}
			if(single==false){
				cout<<a<<endl;
				break;
			}
			int num = a[i]-'0';
			sum+=num*q[i+1];
		}
		if(single == false) continue;
		zz = sum%mod;
		if(check(zz,a[17])){
			
		}
		else{
			all = false;
			single = false;
			cout<<a<<endl;
			continue;
		}
		
	}
	if(all==true) cout<<"All passed";
	return 0;
}

T3 帅到没朋友(模拟）

题目：

代码：

#include <iostream>
#include <cstring>
using namespace std;
int n,q,t,x,f[100005],v[100005];
void init(){
	memset(v,0,sizeof(v));
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		init();
		cin>>t;
		for(int i=1;i<=t;i++){
			cin>>x;
			if(v[x]) f[x]--;
			else f[x]+=t-1,v[x]=1;
		}
	}
	bool sp=true;
	cin>>q;
	while(q--){
		cin>>t;
		if(f[t]==-1) continue;
		if(!f[t])
			cout<<t<<' ',sp=false,f[t]=-1;
	}
	if(sp) cout<<"No one is handsome";
}

T4 输出GPLT（模拟）

题目：

代码：

#include <iostream>
using namespace std;
char s[8]={'G','P','L','T','g','p','l','t'};
int cnt[5],tot;
int main(){
	string a;
	cin>>a;
	for(int i=0;i<a.length();i++) 
		for(int j=0;j<4;j++){
			if(a[i]==s[j]||a[i]==s[j+4]){
				cnt[j]++;
				tot++;
			}
		}
	int i=0;
	while(tot--){
		while(!cnt[i]){
			i++;
			i%=4;
		}
		cout<<s[i];
		cnt[i]--,i++,i%=4;
	}
	return 0;
}

T5 判断素数（暴力）

题目：

代码：

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	int t; cin>>t;
	while(t--){
		bool no=false;
		long long int num;
		cin>>num; if(num==1){
			cout<<"No"<<endl;
			continue;
		}
		for(int i=2;i<=sqrt(num);i++){
			if(num%i==0){
				no=true;
				break;
			}
		}
		if(no==true) cout<<"No"<<'\n';
		else cout<<"Yes"<<'\n';
	}
	return 0;
}

T6 最佳情侣身高差（签到）

题目：

代码：

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	int t; cin>>t;
	while(t--){
		char a; cin>>a;
		double h; cin>>h;
		if(a=='M') printf("%.2lf\n",h/1.09);
		else printf("%.2lf\n",h*1.09);
	}
	return 0;
}

T7 连续因子（数学）

题目：

求连续因子，N的上界是2^31，所以只需要遍历sqrt（2^31）≈ 5e4次去更新答案即可。注意特判质数的情况，因子只有一个即为它本身。

代码：

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	int ans1=0,st;
	int n; cin>>n;
	for(int i=2;i<sqrt(n);i++){
		int num=n,now = i;
		int cnt = 0;
		while(num%now==0){
			cnt++;
			num/=now;
			now++;
		}
		if(ans1 < cnt){
			ans1 = cnt;
			st = i;
		}
	}
	if(ans1){
		cout<<ans1<<endl<<st;
		for(int i=1;i<ans1;i++) cout<<"*"<<st+i;
	}
	else cout<<"1"<<endl<<n;
}

L2-1 红色警报

题目:

样例：

用搜索+并查集判断连通块数量，重要的城市被摧毁时连通块会增多。

代码：

#include <iostream>
#include <cstring>
using namespace std;
int n,m,k,a[505][505],vis[505],f[505],c[505],d[505];
bool calc(int dest){
	bool b1[505],b2[505];//backet
	memset(b1,0,sizeof(b1));
	memset(b2,0,sizeof(b2));
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++){
		if(!b1[f[i]]){
			b1[f[i]]=1;
			cnt1++;
		}
		if(!b2[c[i]]){
			b2[c[i]]=1;
			cnt2++;
		}
	}
	if(cnt1!=cnt2) return false;
	else return true;
}//qiu lian tong kuai
void cpy(){
	for(int i=1;i<=n;i++){
		c[i] = f[i];
	}
}
void init(){
	for(int i=1;i<=500;i++) f[i]=i;
}
int getf(int v){
	if(f[v]==v) return v;
	else{
		f[v] = getf(f[v]);
		return f[v];
	}
}
void merge(int x,int y){
	x = getf(x);
	y = getf(y);
	if(x<=y) f[x] = y;
	else f[y] = x;
}
void dfs(int x){
	for(int i=1;i<=n;i++){
		if((vis[i]==0)&&(a[x][i]==1)&&(d[505]==false)){
			merge(x,i);
			vis[i]=1;
			dfs(i);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++){
		int st,ed;
		cin>>st>>ed;
		st++,ed++;
		a[st][ed]=1;
		a[ed][st]=1;
	}
	dfs(1);
	
	cin>>k;
	for(int i=1;i<=k;i++){
		init();
		memset(vis,0,sizeof(vis));
		int temp; cin>>temp; temp++;
		d[temp] = 1;
		for(int j=1;j<=n;j++)
		dfs(j);//new f[i]
		if(calc(temp)){
			printf("City %d is lost!\n",temp-1);
		}
		else if((!calc(temp))&&(i==k&&k==n)){
			printf("Red Alert: City %d is lost!\n",temp-1);
		}
		else{
			cout<<"Game Over"<<'\n';
		}
		cpy();
	}
	return 0;
}

题目：

代码：

#include <iostream>
int main(){
    int t=3;
    while(t--) std::cout<<"I'm gonna Win!"<<'\n';
    return 0;
}

T2 日期格式化

题目：

#include <bits/stdc++.h>
using namespace std;
int main(){
	int m,d,y;
	cin>>m;
	getchar();//读入时跳过 ‘-’ 符号
	cin>>d;
	getchar();
	cin>>y;
	getchar();
	cout<<y<<"-";
	if(m<10) cout<<"0"<<m<<"-";
	else cout<<m<<"-";
	if(d<10)cout<<"0"<<d;
	else cout<<d;
	return 0;
}

T3 大笨钟

题目：

代码：

#include <bits/stdc++.h>
using namespace std;
stack <int > z;
int main(){
	int h,m;
	cin>>h; getchar(); cin>>m;
	if((h<12)||(h==12&&m==0)){
		cout<<"Only ";
		if(h<10) {
			cout<<"0"<<h<<":";
		} else cout<<h<<":";
		if(m<10){
			cout<<"0"<<m;
		} else cout<<m;
		cout<<".  Too early to Dang.";
	}
	else{
		h-=12;
		if(m!=0) h++;
		while(h--) cout<<"Dang";
	}
	return 0;
}

T4 拯救外星人

题目：

代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	long long int a,b,ans=1;
	cin>>a>>b;
	a+=b;
	for(int i=1;i<=a;i++){
		ans*=i;
	}
	cout<<ans;
	return 0;
}

T5 个位数统计

题目：

代码：

#include <bits/stdc++.h>
using namespace std;
int m[11];
int main(){
	char n;
	while(cin>>n){
		m[n-'0']++;
	}
	for(int i=0;i<=9;i++){
			m[i]? (cout<<i<<":"<<m[i]<<endl) : continue;
	}
	return 0;
}

T6 正整数

题目：

这是孬的模拟，数据读入上会造成很大的麻烦，因为L部分和R部分可能存在非数字的字符所以不能够直接读入整型变量里。为了好定位第一个空格的位置，方便判断L部分的合法性，我用了单字符逐个读入的方法，遇到空格时停止。然后再将输入数据的剩余部分全部读入到R部分中，再逐个判断。代码当然没有必要写的那么复杂，不过我也懒得改了就是； ；

#include <bits/stdc++.h>
using namespace std;
bool rno,lno;
int main(){
	string a="",b="";
	char temp;
	while(temp=getchar()){
		if(isspace(temp)){
			break;
		}
		a = a+temp;
	}
	getline(cin,b);

	if(a.length()>4) lno=true;
	if(b.length()>4) rno=true;
	int lnum=0,rnum=0;
	
	for(int i=0;i<a.length();i++){
		if(a[i]>='0'&&a[i]<='9'){
			if(lnum==0&&((a[i]-'0')==0)){
				lno=true;
				break;
			}
			lnum*=10;
			lnum+=a[i]-'0';
		}
		else{
			lno=true;
			break;
		}
	}
	for(int i=0;i<b.length();i++){
		if(b[i]>='0'&&b[i]<='9'){
			if(rnum==0&&(b[i]-'0'==0)){
				rno=true;
				break;
			}
			rnum*=10;
			rnum+=b[i]-'0';
		}
		else{
			rno=true;
			break;
		}
	}
	if(lnum>1000||lnum<1) lno=true;
	if(rnum>1000||rnum<1) rno=true;
	if(lno==false) cout<<lnum;
	else cout<<"?";
	
	cout<<" + ";
	
	if(rno==false) cout<<rnum;
	else cout<<"?";
	cout<<" = ";
	if(lno==true||rno==true)
		cout<<"?";
	else cout<<lnum+rnum;
	
//	cout<<endl<<lno<<" "<<rno;
}

T7 打印沙漏

题目：

要先算出能够打印出的层数，然后用层数变量控制符号与空格的数量（注意到第i层有 2i 个空格，2（max-i）-1 个符号），由于上下层是对称的，所以我的做法是直接打一半，另一半以字符串的形式存在栈里，很方便。

代码：

#include <iostream>
#include <stack>
using namespace std;
stack <string > a;
int n;
char f;
int main(){
	cin>>n; cin>>f;
	int h;
	for(int i=1;i<=99999;i++){
		if(i*i*2-1>n){
			h = i-1;
			break;
		}
	}
	int remain = n - h*h*2 +1;
	for(int i=1;i<=h;i++){
		string temp="";
		for(int j=1;j<i;j++) temp = " "+temp;
		for(int j=1;j<=(h-i+1)*2-1;j++) temp = temp + f;
		cout<<temp<<endl;
		a.push(temp);
	}
	a.pop();
	while(!a.empty()){
		cout<<a.top()<<endl;
		a.pop();
	}
	cout<<remain;
	return 0;
}

T8 机工士姆斯塔迪奥

题目：

代码：

#include <iostream>
using namespace std;
long long int row[100005],line[100005],tot,n,m,q,t,eaten,stat,r,l;
void prework(){
	cin>>n>>m>>q;
	tot = n*m;
	for(int i=1;i<=q;i++){
		cin>>stat>>t;
		if(stat==0&&row[t]==0)
			r++ , row[t]=1;
		else if(stat==1&&line[t]==0) l++, line[t]=1;
	}
}
void solve(){
	tot = tot + l*r - l*n - r*m;
	cout<<tot;
}
int main(){
	prework();
	solve();
	return 0;
}

L2-1

题目：

样例：

上来写了个领接矩阵，一交WA了。再读一遍题发现漏掉朋友的朋友也是朋友这个条件，敲出并查集提交过了。

#include <iostream>
using namespace std;
bool check;
int n,t,q;
int a[105][105];
int f[105];
void init(){
	for(int i=1;i<=103;i++) f[i]=i;
}
int getf(int x){
	if(f[x]==x) return x;
	else{
		f[x]=getf(f[x]);
		return f[x];
	}
}
void merge(int a,int b){
	a=getf(a);
	b=getf(b);
	if(a!=b){
		f[a]=b;
	}
}
int main(){
	init();
	cin>>n>>t>>q;
	for(int i=1;i<=t;i++){
		int x1,x2,x3;
		cin>>x1>>x2>>x3;
		a[x1][x2]=x3;
		a[x2][x1]=x3;
		if(x3==1) merge(x1,x2);
	}
	for(int i=1;i<=q;i++){
		check = false;
		int x1,x2;
		cin>>x1>>x2;
		if(a[x1][x2]==1) cout<<"No problem"<<endl;
		else if(a[x1][x2]==0) cout<<"OK"<<endl;
		else if(a[x1][x2]==-1){
			for(int i=1;i<=n;i++){
				if(i==x1||i==x2) continue;
				if(getf(x1)==getf(x2)){
					check=true;
				}
			}
			if(check) cout<<"OK but..."<<endl;
			else cout<<"No way"<<endl;
		}
	}
	return 0;
}

L2-2 名人堂与代金券（数据结构）

题目：

样例：

代码：

#include <bits/stdc++.h>
using namespace std;
int n,g,k,ans,cnt;
struct student{
	string email;
	int score;
}stu[100005];
bool cmp(student a,student b){
	if(a.score>b.score)
		return true;
	else if(a.score==b.score){
		if(a.email>b.email){
			return false;
		} 
		else return true;
	}
	else return false;
}

void prework(){
	cin>>n>>g>>k;
	for(int i=1;i<=n;i++){
		cin>>stu[i].email;
		int x2;
		cin>>x2;
		if(x2>=g) ans+=50;
		else if(x2<g&&x2>=60) ans+=20;
		stu[i].score=x2;
	}
	sort(stu+1,stu+n+1,cmp);
}
int main(){
	prework();
	cout<<ans<<endl;
	int rank=1;
	if(k>=1) cout<<rank<<' '<<stu[1].email<<' '<<stu[1].score<<endl;
	cnt++;
	for(int i=2;i<=n;i++){
		if(stu[i].score==stu[i-1].score){
			cnt++;
		}
		else{
			cnt++;
			rank = cnt;
		}
		if(rank<=k)
		cout<<rank<<' '<<stu[i].email<<' '<<stu[i].score<<endl;
		else break;
	}
	return 0;
}

比较函数写的混乱不堪，重写一遍应该是这个样子：

bool cmp(student a,student b){
	if(a.score!=b.score) 
		return a.score>b.score;
	else{
		return a.email<b.email;
	}
}

题目：

f【i】为在i时刻能获得的最大收益。在从1到所有活动最晚的开始时间，用所有i时刻开始的活动更新下一时刻的答案，不断更新答案的值。

#include <iostream>
#include <vector>
using namespace std;
struct rw{
	int end,value;
};
vector <rw> a[1005];
int n,s,e,w,ans,maxe,f[1005];

void prework(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s>>e>>w;
		if(e>maxe) maxe=e;
		rw temp; temp.end=e,temp.value=w;
		a[s].push_back(temp);
	}//存入数据
}

void solve(){
	for(int i=1;i<=maxe;i++){
		if(f[i+1]<f[i])
			f[i+1]=f[i];
		for(int j=0;j<a[i].size();j++){
			rw temp=a[i][j];
			int last = temp.end, earn = temp.value;
			if(f[i]+earn > f[last]) f[last] = f[i]+earn;
		}
		if(f[i]>ans) ans = f[i];
	}
	cout<<ans;
}
int main(){
	prework();
	solve();
	return 0;
}

T2 路径记数

题目：

很基础的dp题。每一种走法都会更靠近右下角，所以在f[i][j] = f[i-1][j] + f[i][j-1]的基础上分类即可，要取模。

#include <iostream>
using namespace std;
const int mod = 1e9+7;
int f[105][105],n,temp;
void prework(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>temp;
			if(temp==0) f[i][j]=-1;
		}
	}
	f[1][1]=1;
}
void solve(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
if(i==1&&j==1) continue;
			if(f[i][j]!=-1){
				if(f[i-1][j]!=-1&&f[i][j-1]!=-1){
					f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
				}
				else if(f[i-1][j]==-1&&f[i][j-1]!=-1){
					f[i][j]=(f[i][j-1])%mod;
				}
				else if(f[i-1][j]!=-1&&f[i][j-1]==-1){
					f[i][j]=(f[i-1][j])%mod;
				}
				else continue;
			}
		}
	}
	cout<<(f[n][n])%mod;
}
int main(){
	prework();
	solve();
	return 0;
}

T3 最大和上升子序列

题目：

#include <iostream>
using namespace std;
long long int n,a[1005],b[1005],ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	for(int i=2;i<=n;i++){
		b[i]=a[i];
		for(int j=i;j>=1;j--){
			if((a[i]>a[j])&&(a[i]+b[j])>b[i]){
				b[i]=a[i]+b[j];
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(b[i]>ans) ans=b[i];
	}
	cout<<ans;
	return 0;
}

T4 Alice的德州扑克

题目：

是模拟题，判断每一种情况后输出即可。

#include <iostream>
using namespace std;
int a[9],b[9];
bool dk,no1,no2,no3,no4,no5;
int cnt1,cnt2,cnt3;
int main(){
	for(int i=1;i<=5;++i) cin>>a[i];
	cin>>b[1];
	for(int i=2;i<=5;++i){
		cin>>b[i];
		if(b[i]!=b[1]) dk=true;
	}
	
	for(int i=1;i<=4;i++){
		if(a[i]!=a[i+1]-1){
			no1=true;
			break;
		}
	}
	if(no1==false&&dk==false&&a[5]==14){
		cout<<"ROYAL FLUSH"; return 0;
	}
	else if(no1==false&&dk==false){
		cout<<"STRAIGHT FLUSH"; return 0;
	}
	if(a[1]==a[2]&&a[2]==a[3]&&a[3]==a[4]&&a[5]!=a[4]){
		cout<<"FOUR OF A KIND"; return 0;
	}
	if(a[5]==a[4]&&a[2]==a[3]&&a[3]==a[4]&&a[1]!=a[2]){
		cout<<"FOUR OF A KIND"; return 0;
	}
	if((a[1]==a[2])&&((a[3]==a[4])&&(a[4]==a[5]))){
		cout<<"FULL HOUSE"; return 0;
	}
	if((a[4]==a[5])&&((a[3]==a[2])&&(a[2]==a[1]))){
		cout<<"FULL HOUSE"; return 0;
	}
	
	if(dk==false){
		cout<<"FLUSH"; return 0;
	}
	
	if(no1==false){
		cout<<"STRAIGHT"; return 0;
	}
	cout<<"FOLD"; return 0;
}

T5 分数统计

题目：

是道模拟题，适合用来练习stl中的map容器，能快速排掉无效的人名，查找，删改复杂度为O(logn)。

#include <iostream>
#include <map>
using namespace std;
int n,t,k;
map<string,int> grade;
map<string,int> problem;
string name[205];
void prework(){
	cin>>n>>t>>k;
	for(int i=1;i<=n;i++){
		string temp;
		cin>>temp;
		name[i]=temp;
		grade.insert({temp,0});
	}//¶ÁÈ¡Êý¾Ý
	for(int i=1;i<=t;i++){
		string temp;
		int score;
		cin>>temp>>score;
		problem.insert({temp,score});
	}
}

void solve(){
	for(int i=1;i<=k;i++){
		string tempname,temppro,stat,s1;
		cin>>tempname>>temppro>>stat;
		if(stat=="WA") continue;
		
		map<string,int>::iterator it1;
		it1=grade.find(tempname);
//		(it1==grade.end()) ? continue; : string s1=it1->first;
		if(it1==grade.end())
			continue;
		else{
			s1=it1->first;
			//´æ´¢Ãû×Ö 
		}
		
		map<string,int>::iterator it2;
		it2=problem.find(temppro);
		int scorer=it2->second;
		grade[s1]+=scorer;
	}
}

int main(){
	prework();
	solve();
	map<string,int>::iterator it;
	for(int i=1;i<=n;i++){
		it = grade.find(name[i]);
		cout<<name[i]<<' '<<it->second<<endl;
	}
	return 0;
}

题目：

是一道简单的dp题，可以压缩成一维数组。

#include <iostream>
using namespace std;
int main()
{
	long long int n,a[55];
	cin>>n;
	a[0]=1,a[1]=1,a[2]=2;
	for(int i=3;i<=50;i++){
		if(i<=5) a[i]=a[i-1]+a[i-2];
		else a[i]=a[i-1]+a[i-3]+a[i-5];
	}
	cout<<a[n];
	return 0;
}

T2 走路

题目：

也是一道dp题

#include <iostream>
using namespace std;
int n,m,a[105],b[105],dp[105][100005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(j-a[i]>=0){
				dp[i][j] |= dp[i-1][j-a[i]];
			}
			if(j-b[i]>=0){
				dp[i][j] |= dp[i-1][j-b[i]];
			}
		}
	}
	for(int i=0;i<=m;i++)
	cout<<dp[n][i];
	return 0;
}

T3 订单编号

题目：

样例：

可以用并查集存x对应的最小的编号。（这里用unordered_map 才能过 是可能会被卡的O(1),map复杂度是lO（logn）,对排序没有什么需求时可以用unordered_map）

#include <bits/stdc++.h>
using namespace std;
int a[10000005],n;
unordered_map <int,int> f;
int find(int x){
	if(f[x]==0) f[x]=x;
	if(f[x]!=x) f[x]=find(f[x]);
	return f[x];
}
void merge(int x,int y){

	x=find(x);
	y=find(y);
	f[x]=y; 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		cout<<find(a[i])<<' ';
		merge(a[i],f[a[i]]+1);
	}
	return 0;
}

T5 饿饿 饭饭

题目：

样例：

设最多可以打x轮，然后减去x-1轮后的情况，对最后一轮进行模拟即可。（求轮数x应该用二分去做）

#include <iostream>
using namespace std;
long long int n,k,a[100005],tot,sum,ans[100005];
bool check(int x){
	long long int p=0;
	for(int i=1;i<=n;i++){
		p += (a[i]>=x ?  x : a[i]);
	}
	if(p<=k) return true;
	else return false;
}//计算出能打x轮
void calc(int x){
	sum=0;
	for(int i=1;i<=n;i++){
		sum +=(a[i]>=x ? x : a[i]);
		a[i] -= x;//减去l轮的饭量
	}
}
void prework(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		tot+=a[i];//学生总饭量
	}
}
void solve(){
	int l=0,r=2e9,mid;
	while(l+1<r){
		mid = (l+r)/2;
		if(check(mid)){
			l = mid;
		}
		else r = mid;
	}//此时l为最后一轮前一轮的轮数
	calc(l);
	k-=sum;//剩余的打饭量
	//进行最后一轮的打饭
	int stop;
	int cnt=1;
	for(int i=1;i<=n;i++){
		if(k==0){
			stop = i;
			break;
			//打完了
		}
		if(a[i]>1){
			ans[cnt] = i;
			cnt++;
			k--;
		}
		else if(a[i]==1){
			k--;
		}
	}
//cout<<l<<endl<<k<<endl<<stop<<endl;
	for(int i=stop;i<=n;i++){
		if(a[i]>=1){
			cout<<i<<' ';
		}
	}
	for(int i=1;i<cnt;i++) cout<<ans[i]<<" ";
}
int main(){
	prework();
	if(tot<k){
		cout<<"-1";
		return 0;
	}
	if(tot==k) return 0;
	solve();
	return 0;
}

未优化，当成多重背包做。

#include <iostream>
#include <stdio.h>
using namespace std;
int v[1005],w[1005],s[1005],dp[1005];
int main(){
	freopen("P1776_4.in","r",stdin);
	int N,V;
	cin>>N>>V;
	for(int i=1;i<=N;i++){
		cin>>w[i]>>v[i]>>s[i];
	}
	for(int i=1;i<=N;i++){
		for(int k=V;k>=1;k--){
			for(int l=0;l<=s[i]&&l*v[i]<=k;l++){
				cout<<k<<' '<<k-l*v[i]<<' ';
				dp[k]=max(dp[k],dp[k-l*v[i]]+l*w[i]);
			}
		}
	}
	cout<<dp[V];
	return 0;
}

二进制优化后（节省了大量空间）

#include <iostream>
#include <stdio.h>
using namespace std;
const int maxx=1e7+5;
int N,V;
int v[12005],w[12006],dp[maxx];
int main(){
//	freopen("P1776_4.in","r",stdin);
	cin>>N>>V;
	int count=0;
	//分成2^0(1),2^1(2),2^2(4),2^3(8)...余数组。
	//O(n^3)->O(n^2logS）
	for(int i=1;i<=N;++i){
		int z,x,c;
		cin>>z>>x>>c;
		for(int k=1;k<=c;k*=2){
			count++;
			v[count]=x*k;//fu gai.?
			w[count]=z*k;
			c-=k;
		}
		if(c>0){
			count++;
			v[count]=x*c;
			w[count]=z*c;
		}
	}
	//拿1024次苹果或者拿10次。（7次？
	for(int i=1;i<=count;++i){
		for(int k=V;k>=1;k--){
			if(k>=v[i])
			dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

T2 尴尬的数字（P1555）

#include <iostream>
using namespace std;
string a,b;
int cvs(string x){
	int yu,temp=0;
	for(int i=0;i<x.length();i++){
		yu=x[i]-'0';
		temp*=10;
		temp+=yu;
	}
	return temp;
}//转换数据类型
string er_shi(string x){
	int len=x.length(),baka;
	int i=0;
	if(x[i]!='0')
		baka=x[0]-'0';
	else{
		baka=x[1]-'0';
		i++;
	}
	i++;
	for(;i<len;i++){
		baka*=2;
		baka+=x[i]-'0';
	}
	string back;
	char temp;
	while(baka){
		temp=(baka%10)+'0';
		back=temp+back;
		baka/=10;
	}
	return back;
}//二进制转十进制
string shi_san(string x){
	string back;
	int num=cvs(x);//
	int yu;
	char temp;
	while(num){
		yu=num%3;
		temp=yu+'0';
		back=temp+back;
		num/=3;
	}
	return back;
}//十进制转三进制
bool cmp(string x){
	if(x.length()!=b.length())
		return false;
	int cnt=0;
	for(int i=0;i<b.length();i++){
		if(x[i]!=b[i])
			cnt++;
	}
	if(cnt==1) return true;
	return false;
}//判断函数
void change(int x){
	if(a[x]=='1') a[x]='0';
	else a[x]='1';
}
int main(){
	cin>>a>>b;
	for(int i=0;i<a.length();i++){
		if(i==0){
			change(i);
		}
		else{
			change(i-1);
			change(i);
		}//更换数字
		//此时是二进制字符串
		int ans=-1;
		ans=cvs(er_shi(a));//保存答案
		if(cmp(shi_san(er_shi(a)))){
			cout<<ans;
			return 0;
		}
		else continue;
	}
	return 0;
}

T3 小卡和质数（P8845）

#include <iostream>
int main(){
	int t,a,b;
	std::cin>>t;
	while(t--){
		std::cin>>a>>b;
		if((a==1&&b==2)||(a==2&&b==1)) std::cout<<"Yes"<<std::endl;
		else std::cout<<"No"<<std::endl;
	}
	return 0;
}

#include <iostream>
using namespace std;
const int inf=1e9+5;
int n,t,ans;
int c[105][105][105],dp[105][105],planet[105];
//c(i,j,k)表示从等级为i编号为j的星球走到等级为i+1编号为k星球的代价
//dp(i,j)表示走到等级为i编号为j的星球的代价
//状态转移方程：dp(i,j)=min(dp(i-1,l)+c,dp(i,j))
void init(){
	for(int i=1;i<=103;i++)
	for(int l=1;l<=103;l++)
	dp[i][l]=inf;
	for(int i=1;i<=103;i++)
	for(int l=1;l<=103;l++)
	for(int k=1;k<=103;k++)
	c[i][l][k]=inf;
	planet[0]=1;
}
int main(){
	init();
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t;
		planet[i]=t;
		int cnt=1;
		while(t--){
			int st,v,z;
			cin>>st>>v>>z;
			c[i-1][st][cnt]=v;
			while(z!=0){
				st=z;
				cin>>v>>z;
				if(c[i-1][st][cnt]>v)//你妈的有重边
				c[i-1][st][cnt]=v;
			}
			cnt++;//到达的等级为i的星球编号
		}
	}
	dp[0][1]=0;
	for(int i=1;i<=n;i++){
		for(int l=1;l<=planet[i];l++){
			for(int k=1;k<=planet[i-1];k++){
				if(c[i-1][k][l]==inf) continue;
				dp[i][l]=min(dp[i][l],dp[i-1][k]+c[i-1][k][l]);
			}
		}
	}
	ans=inf;
	for(int i=1;i<=planet[n];i++)
	ans=min(ans,dp[n][i]);
	cout<<ans;
	return 0;
}

T2 跑步（P1806）

#include<iostream>
using namespace std;
long long int n,ans,dp[505][505];
void init(){
	for(int i=1;i<3;i++)
	for(int l=1;l<=500;l++)
	dp[i][l]=0;
}
long long int sum_(int row,int x){
	long long int sum=0;
	for(int k=x;k<=500;k++)
	sum+=dp[row][k];
	return sum;
}
int main(){
	cin>>n;
	for(int i=1;i<=500;i++){
		for(int l=1;l<=500;l++){
			if((i%2!=0&&l>i/2)||(i%2==0&&l>=i/2)) break;
			dp[i][l]=sum_(i-l,l+1)+1;
		}
	}
	for(int i=1;i<=500;i++)
	ans+=dp[n][i];
	cout<<ans;
	return 0;
}

T3 砝码称重(P8742)

#include <iostream>
#include <cmath>
using namespace std;
int n,w[105],max_,ans;
bool dp[105][300005];
void prework(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i];
		max_=max_+w[i];
	}
	dp[0][0]=1;
}
void solve(){
	for(int i=1;i<=n;i++){
		for(int l=1;l<=max_;l++){
			dp[i][l]=dp[i-1][l];
			if(w[i]==l) 
			dp[i][l]=1;
			else if(dp[i-1][l+w[i]]==1)
			dp[i][l]=1;
			else if(dp[i-1][abs(l-w[i])]==1)
			dp[i][l]=1;
			if(dp[n][l]==1) ans++;
		}
	}
	cout<<ans;
}
int main(){
	prework();
	solve();
	return 0;
}

T4 遗址（P1959）

#include <iostream>
#include <cmath>
using namespace std;
struct edge{
	int x,y;
}a[3005];
int n,ans;
bool vis[5005][5005];
void check(int x1,int y1,int x2,int y2){
	int yy=abs(y1-y2);
	int xx=abs(x1-x2);
	int x3=x2+yy;
	int y3=y2+xx;
	int x4=x1+yy;
	int y4=y1+xx;
	if(x3<=5000&&y3<=5000&&x4<=5000&&y4<=5000&&vis[x3][y3]&&vis[x4][y4]){
		int temp=xx*xx+yy*yy;
		if(temp>ans) ans=temp;
	}
	x3=x2-yy;
	y3=y2-xx;
	x4=x1-yy;
	y4=y1-xx;
	if(x3>=0&&y3>=0&&x4>=0&&y4>=0&&vis[x3][y3]&&vis[x4][y4]){
		int temp=xx*xx+yy*yy;
		if(temp>ans) ans=temp;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int xx,yy;
		cin>>xx>>yy;
		vis[xx][yy]=true;
		a[i].x=xx;
		a[i].y=yy;
	}//读入数据
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			check(a[i].x,a[i].y,a[j].x,a[j].y);
		}
	}
	cout<<ans;
	return 0;
}

T5 环境治理（P8794）

#include <iostream>
using namespace std;
int n,q,max,cnt;
int map[105][105],work[105][105];
int lmt[105][105];
bool checklmt(){
	for(int i=0;i<n;i++)
	for(int l=0;l<n;l++)
	work[i][l]=lmt[i][l];
	for(int k=0;k<n;k++)
		for(int i=0;i<n;i++)
			for(int l=0;l<n;l++){
				if(i==l) continue;
				if(work[i][l]>work[k][l]+work[i][k])
				work[i][l]=work[k][l]+work[i][k];
				}
	int sum_=0;
	for(int i=0;i<n;i++)
	for(int l=0;l<n;l++)
	sum_+=work[i][l];
	if(sum_<=q) return true;
	return false;
}
void init(){
	for(int i=0;i<n;i++)
	for(int l=0;l<n;l++)
	work[i][l]=map[i][l];
}
int sum(){
	int ans=0;//加和前初始化
	for(int i=0;i<n;i++)
		for(int l=0;l<n;l++)
		ans+=work[i][l];
		return ans;
}
void prework(){
	cin>>n>>q;
	for(int i=0;i<n;i++)
		for(int l=0;l<n;l++)
			cin>>map[i][l];
	for(int i=0;i<n;i++)
		for(int l=0;l<n;l++)
			cin>>lmt[i][l];
}
bool floyd(){
	init();//初始化
	for(int k=0;k<n;k++)
		for(int i=0;i<n;i++)
			for(int l=0;l<n;l++){
				if(i==l) continue;
				if(work[i][l]>work[k][l]+work[i][k])
				work[i][l]=work[k][l]+work[i][k];
			}
			if(sum()<=q) return false;
			return true;
}
void solve(){
	while(floyd()){
		int row=cnt%n;
		for(int i=0;i<n;i++){
			if(map[row][i]>lmt[row][i])
			map[row][i]--;
		}
		cnt++;
	}
	cout<<cnt;
}
int main(){
	prework();
	if(!checklmt()){
		cout<<"-1";
		return 0;
	}
	solve();
	return 0;
}

是一题（一笔画）欧拉路的模板。欧拉路 是指若从起点到终点的路径恰经过图中每条边一次，则该路径成为欧拉路。存在欧拉路的条件是：图是联通的，且有0个或2个奇点（出入度为奇数的点）。欧拉路一定是从一个奇点开始，到另一个奇点结束，所以有两个奇点的时候能一笔画完。

若每多出两个奇点，画的次数就会+1，所以答案就是 奇点的个数 / 2。

//当一个无向图的奇点数为0或者2的时候
//可以不重边的走完所有点
//奇点为度为奇数的点
//所以一幅图要（奇点数/2）笔画完
#include <iostream>
using namespace std;
int du[1005];//统计一个点的度数
int main(){
	int n,m; cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,e;
		cin>>s>>e;
		du[s]++;
		du[e]++;
		//无向图，所以出入度相等
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(du[i]%2)
		ans++;
		if(ans==0) cout<<"1";//小特判
		else cout<<ans/2;
		return 0;
}

T2 合根植物（并查集）

是一道并查集的板子题，需要路径压缩。

#include <iostream>
using namespace std;
int n,m,k;
int f[1000005];
void init(){
	for(int i=1;i<=1000000;i++)
	f[i]=i;
	return;
}//初始化是必须的
int getf(int v){
	if(f[v]==v)
	return v;//查找根节点
	else{
		f[v]=getf(f[v]);
		return f[v];//路径压缩
	}
}//查找
void merge(int a,int b){
	int b1,b2;
	b1=getf(a);
	b2=getf(b);
	if(b1!=b2){
		f[b2]=b1;
		//左靠原则
	}
	return;
}//合并
int main(){
	cin>>n>>m>>k;
	//n为行数，m为列数
	init();
	for(int i=1;i<=k;i++){
		int x,y;
		cin>>x>>y;
		merge(x,y);
	}
	int sum=0;
	int tot=n*m;
	for(int i=1;i<=tot;i++){
		if(f[i]==i)
		sum++;
	}
	cout<<sum;
	return 0;
}

T3 奶酪

题目可以用dfs进行n^2的遍历，通过两点球心距离和两球半径之和的孰大孰小判断两球是相交，相切还是相离。

#include <iostream>
#include <cmath>
#include <cstring>
#include <stdio.h>
using namespace std;
long long int t,n,h,r;
bool vis[1005],found;
struct ball{
	int x,y,z;
}p[1004];
bool link(ball a,ball b){
	long long int dis=(pow(a.x-b.x,2)+pow(a.y-b.y,2)+pow(a.z-b.z,2));
	//两点距离的平方与2r的平方对比
	if(dis>4*r*r) 
		return false;
	else return true;//如果相交
}
void dfs(int a){
	if(found==true) return;
	if(p[a].z+r>=h){
		found=true;
		return;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==true) continue;
		else{
			if(link(p[a],p[i])){
				vis[i]=true;
				dfs(i);
			}//如果相交
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	cin>>t;
	while(t--){
		found = false;
		memset(vis,false,sizeof(vis));
		//初始化
		cin>>n>>h>>r;
		for(int i=1;i<=n;i++){
			cin>>p[i].x>>p[i].y>>p[i].z;
		}
		for(int i=1;i<=n;i++){
			if(p[i].z<=r){
				dfs(i);
				//如果和底边相交或相切
			}
		}
		if(found==true) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

T4 灾后重建（最短路）

用了动态规划的思想，是一道很好的练习floyd的题。

#include <iostream>
#include <stdio.h>
using namespace std;
const int inf=1e9+5;
int map[205][205];
int n,m,q,t[205];
int st,ed,v;//临时变量
void init(){
	for(int i=0;i<n;i++)
		for(int l=0;l<n;l++){
		map[i][l]=inf;
	}
	for(int i=0;i<n;i++) map[i][i]=0;
}//初始化
void updata(int x){
	for(int i=0;i<n;i++){
		for(int l=0;l<n;l++){
			map[i][l]=min(map[i][l], map[i][x]+map[x][l]);
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	cin>>n>>m;
	init();
	for(int i=0;i<n;i++) cin>>t[i];
	for(int i=0;i<m;i++){
		cin>>st>>ed>>v;
		map[st][ed]=v;
		map[ed][st]=v;
		//存图
	}
	cin>>q;
	int cur=0;
	while(q--){
		cin>>st>>ed>>v;
		while(t[cur]<=v&&cur<n){
			updata(cur);
			cur++;//时间是逐渐变大的，所以已经做过中转的村庄不会再用到
		}
		if(t[st]>v||t[ed]>v||map[st][ed]==inf) cout<<"-1"<<endl;
		else cout<<map[st][ed]<<endl;
	}
	return 0;
}

T5 聪明的猴子

生成树的模板题。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct edge{
	int s,e;
	long long int v;
}p[1000005];
int f[1005];
int x[1005],y[1005];
int M,mk[505],n;
int ans;
int cnt;
int getf(int x){
	if(f[x]==x) return x;
	else{
		f[x]=getf(f[x]);
		return f[x];
	}
}
bool merge(int x,int y){
	int x1,y1;
	x1=getf(x);
	y1=getf(y);
	if(x1!=y1){
		f[x1]=y1;
		return true;
	}
	return false;//已经联通
}
void init(){
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	return;
}
long long int len(int x1,int y1,int x2,int y2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);//返回距离的平方
}
bool cmp(edge a,edge b){
	return a.v<b.v;
}
int main(){
	cin>>M;
	for(int i=1;i<=M;i++){
		int aa; cin>>aa;
		mk[i]=aa*aa;
	}
	sort(mk+1,mk+1+M);
	cin>>n;
	init();
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}//读入数据
	for(int i=1;i<=n;i++){
		for(int l=i+1;l<=n;l++){
			long long int lens;
			lens=len(x[i],y[i],x[l],y[l]);
			cnt++;
			p[cnt].s=i;
			p[cnt].e=l;
			p[cnt].v=lens;
			//读入所有边
		}
	}
	int time=n*(n-1)/2;
	sort(p+1,p+1+time,cmp);//对time条边进行排序
	cnt=0;
	long long int max=0;
	for(int i=1;i<=time;i++){
		if(merge(p[i].s,p[i].e)){
			cnt++;
			max=p[i].v;
		}
		if(cnt==time-1) break;
	}
	for(int i=M;i>=1;i--){
		if(mk[i]>=max) ans++;
		else break;
	}
	cout<<ans;
	return 0;
}

下附代码：

#include <bits/stdc++.h>
using namespace std;
const int maxx=1e6+5;
int n,m;
int vis[maxx];
vector<int> book[maxx];
queue<int> b;
void dfs(int x){
	if(vis[x]==1) return;
	vis[x]=1;
	cout<<x<<' ';
	for(int i=0;i<book[x].size();++i){
		dfs(book[x][i]);
	}
}
void bfs(){
	b.push(1);
	while(!b.empty()){
		int x=b.front();
		b.pop();
		cout<<x<<' ';
		vis[x]=1;
		for(int i=0;i<book[x].size();++i){
			int next=book[x][i];
			if(vis[next]==1) continue;
			else{
				b.push(next);
				vis[next]=1;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int f,e;
		cin>>f>>e;
		book[f].push_back(e);
	}
	for(int i=1;i<=n;i++){
		sort(book[i].begin(),book[i].end());
	}//排序n种资料
	dfs(1);
	cout<<endl;
	memset(vis,0,sizeof(vis));
	bfs();
	return 0;
}

T2 Floyd（最短路n^3模板题）

floyd比较短，本质上是一种dp算法。时间复杂度为 n^3，n<10^3内的数据可以用。floyd适用性也很高，遍历所有点所以可以做到一些生成树算法的功能。

下附代码：

#include <iostream>
#include <cstring>
using namespace std;
const long long int mod = 998244354;
const long long int INF=25e13+500;
int n,m;
long long int ans;
long long int map[505][505];
int main(){
	for(int i=1;i<=503;i++)
	for(int l=1;l<=503;l++){
		if(i==l) map[i][l]=0;
		else map[i][l]=INF;
	}
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,e,v;
		cin>>s>>e>>v;
		if(map[s][e]!=0&&map[s][e]>v){
			map[s][e]=v;
			map[e][s]=v;
		}
		//无向图。
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int l=1;l<=n;l++){
				if(i==l) continue;
				if(map[k][l]<INF&&map[i][k]<INF&&map[i][l]>(map[k][l]+map[i][k]))
				map[i][l]=(map[k][l]+map[i][k]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans=0;
		for(int l=1;l<=n;l++){
			ans+=map[i][l];
			ans%=mod;
		}
		cout<<ans%mod<<endl;
	}
	return 0;
}

T3 单源最短路径（标准版）

用dijkstra时要用堆来优化缩边过程的选点步骤，可以用优先队列来存放到各点的估计值。

各种存图方式，代码用了vector数组进行存图

下附代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int inf=2e9+5;
struct point{
	int end,len;
	bool operator < (const point a) const{
		return len < a.len;
	}//重载运算符
	bool operator > (const point a) const{
		return len > a.len;
	}
};
int n,m,st,cnt,now;
bool book[100005];
vector <point> a[100005];//最多1e5个点
priority_queue <point, vector<point>,greater<point> > dis;
int ans[100005];//存答案的数组。
int main(){
	cin>>n>>m>>st;
	for(int i=1;i<=100005;i++){
		ans[i]=inf;
	}
	ans[st]=0;
	for(int i=1;i<=m;i++){
		int s,e,v;
		cin>>s>>e>>v;
		a[s].push_back({e,v});
	}//vector存图
	dis.push({st,0});//存入起点
	while(!dis.empty()){
		point temp=dis.top();
		dis.pop();
		now=temp.end;
		//因为确定值不能重复更新（优先队列内仍可能存在
		//所以要加一个判断。
		if(!book[now]){
			book[now]=true;
			for(int i=0;i<a[now].size();i++){
				//遍历所有边 vector下标从0开始
				point x=a[now][i];
				int to=x.end;
				int v=x.len;
				//dijkstra核心代码
				if(ans[to]>ans[now]+v){
					ans[to]=ans[now]+v;
				//dijkstra核心代码
					if(!book[to]){
						//减少判断次数，去掉不影响算法正确性。
						dis.push({to,ans[to]});
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<' ';
	}
	return 0;
}

太典了。

大家闭着眼睛都能敲出来。（？）

#include <iostream>
using namespace std;
int T,M;
int t[1005],v[1005],dp[1005];
int main(){
	cin>>T>>M;
	for(int i=1;i<=M;i++){
		cin>>t[i]>>v[i];
	}
	
	for(int i=1;i<=M;i++){
		for(int p=T;p>=1;p--){
			if(p>=t[i]){
				dp[p]=max(dp[p],dp[p-t[i]]+v[i]);
			}
		}
	}
	cout<<dp[T];
}

T2 最长上升子序列

题目：

逆向防御导弹？）

#include <iostream>
using namespace std;
const int N=1e6+5;
int n;
int num[5005];
int dp[5005];
int ans=1;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		for(int j=i-1;j>=1;j--){
			if(num[j]<num[i]&&dp[i]<dp[j]+1){
				dp[i]=dp[j]+1;
			}
		}
		if(dp[i]==0)
		dp[i]=1;
		if(dp[i]>ans) ans=dp[i];
	}
	cout<<ans;
	return 0;
}

T3 最大序列和

题目：

更新的式子同样很好找到。

要注意的只是判断的条件而已。

#include <iostream>
using namespace std;
int n,ans=-999999;
int num[200005],dp[200005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		dp[i]=num[i];
		if(i!=1&&dp[i-1]>=0){
			dp[i]=dp[i]+dp[i-1];
		}
		if(dp[i]>ans) ans=dp[i];
	}
	cout<<ans;
	return 0;
}

T4 LCS

太典了，啧啧啧。

也是大家闭着眼睛也能敲出来的东西（？）

#include <bits/stdc++.h>
using namespace std;
int dp[3005][3005];
int max_,a1,b1;
string ans;
int main(){
	string a,b;
	getline(cin,a);
	getline(cin,b);
	int len1=a.length();
	int len2=b.length();
	//矩阵边边要从0开始，下标0为dp中的1.
	for(int i=0;i<len1;i++){
		for(int l=0;l<len2;l++){
			if(a[i]==b[l]) dp[i+1][l+1]=dp[i][l]+1;
			else dp[i+1][l+1]=max(dp[i][l+1],dp[i+1][l]);
			if(dp[i+1][l+1]>max_){
				max_=dp[i+1][l+1];
				a1=i+1;
				b1=l+1;
			}
		}	
	}
	while(a1>0&&b1>0){
		if(a[a1-1]==b[b1-1]){
			ans=a[a1-1]+ans;
			a1-=1;
			b1-=1;
		}
		else{
			if(dp[a1-1][b1]>dp[a1][b1-1])
			a1-=1;
			else
			b1-=1;
		}
	}
	cout<<ans;
}

题目：

是经典的01背包问题，在博客另一处有介绍，推出 状态转移方程即可。

代码如下。

#include <iostream>
using namespace std;
long long int T,n;
long long int t[10005],w[10005];
long long int dp[10000005];
int main(){
	cin>>T>>n;
	for(int i=1;i<=n;i++) 
	cin>>t[i]>>w[i];
	for(int i=1;i<=n;i++){
		for(int l=1;l<=T;l++){
			if(l>=t[i])
			dp[l]=max(dp[l],dp[l-t[i]]+w[i]);
		}
	}
	cout<<dp[T];
	return 0;
}

T2 摆花

题目：

计数dp

用填表法的思想可以得出更新dp数组的式子。

#include <iostream>
using namespace std;
const long long int x=1000007;
long long int n,m,a[104],dp[105][105];
//dp[i][j]记录有i种花，要摆j盆时的摆法。
int main(){
	dp[0][0]=1;//一种花都没有的话是一种情况。
	cin>>n>>m;
	for(long long int i=1;i<=n;i++)
	cin>>a[i];
	for(long long int i=1;i<=n;i++){
		for(long long int l=0;l<=m;l++){
			for(long long int p=0;p<=min(l,a[i]);p++){
				dp[i][l]=(dp[i][l]+dp[i-1][l-p])%x;//每次都取模。
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}

T3 樱花

题目：

看题可以知道有些美学值是可以拿很多甚至无限次的，所以这是一个多重背包问题，可以用二进制优化将复杂度由O（n^3）优化至O（n^2 logn）

可以把没有次数限制的美学值次数设成一个比较大的数。

代码如下。

#include <bits/stdc++.h>
using namespace std;
int N,V;
int v[100000005],w[100000006],dp[100000005];
long long int hs,ms,he,me;
int main(){
	scanf("%lld:%lld %lld:%lld %lld",&hs,&ms,&he,&me,&N);
	he-=hs;
	if(me-ms<0)
	me=me-ms+60,he--,me+=he*60;
	else me = me - ms + he * 60;
	V=me;
	int count=0;
	//分成2^0(1),2^1(2),2^2(4),2^3(8)...余数组。
	//O(n^3)->O(n^2logS）
	for(int i=1;i<=N;++i){
		int z,x,c;
		cin>>z>>x>>c;
		if(c==0) c=9999999;
		for(int k=1;k<=c;k*=2){
			count++;
			v[count]=z*k;
			w[count]=x*k;
			c-=k;
		}
		if(c>0){
			count++;
			v[count]=z*c;
			w[count]=x*c;
		}
	}
	for(int i=1;i<=count;++i){
		for(int k=V;k>=0;k--){
			if(k>=v[i])
			dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

T4 金明的预算方案

题目：

这题存附件数据技巧是开二维数组cost[x][y],x为第x件物品，当y为0时为这件物品本身，y为1时为第x件物品的附件1，y为2时为第x件物品的附件2。

然后每次选择有五种情况，

①只买主件
②买主件+附件1
③买主件+附件2
④买主件+附件1+附件2
⑤不买主件。

除了1和5冲突外，其他四个都能判断后更新新的dp值，顺序任意，枚举这五种情况，填表即可。

代码如下。

#include <iostream>
#include <cstring>
using namespace std;
int m,n;
int dp[70][40000];
int cost[70][5],imp[70][5];
int main(){
	cin>>m>>n;
	int c,im,f;
	for(int i=1;i<=n;i++){
		cin>>c>>im>>f;
		if(!f){
			cost[i][0]=c;
			imp[i][0]=im;
		}
		else{
			if(!cost[f][1]){
				cost[f][1]=c;
				imp[f][1]=im;
			}
			else{
				cost[f][2]=c;
				imp[f][2]=im;
			}
		}
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			if(l-cost[i][0]>=0){
				dp[i][l]=max(dp[i-1][l],dp[i-1][l-cost[i][0]]+cost[i][0]*imp[i][0]);
				if(l-cost[i][0]-cost[i][1]>=0){
				dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][1]]+cost[i][0]*imp[i][0]+cost[i][1]*imp[i][1]);
				}
				if(l-cost[i][0]-cost[i][2]>=0){
				dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][2]]+cost[i][0]*imp[i][0]+cost[i][2]*imp[i][2]);
				}
				if(l-cost[i][0]-cost[i][1]-cost[i][2]>=0){
					dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][1]-cost[i][2]]+cost[i][0]*imp[i][0]+cost[i][1]*imp[i][1]+cost[i][2]*imp[i][2]);
				}
			}
			else
			dp[i][l]=dp[i-1][l];
		}
	}
	cout<<dp[n][m];
	return 0;
}

总结：

记忆化搜索>dp？）。
代码写的好丑呀。（不是什么大问题就是）