代码源 T6-T8(week 14)

发布于 2023-05-13  199 次阅读


T1 任务分配

题目:

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