五题(week12)

发布于 2023-05-12  103 次阅读


T1 汤姆斯的天堂梦(P1796)

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