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