题目：

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;
}