最长公共子序列
#include<iostream> #include<string> #include<cmath> using namespace std; string a,b; int dp[210][210]; int main(){ cin>>a>>b; int sa=a.size(),sb=b.size(); for(int i=1;i<=sa;i++){ for(int j=1;j<=sb;j++){ if(a[i-1]==b[j-1])dp[i][j]=dp[i-1][j-1]+1; else{ dp[i][j]=max(dp[i][j-1],dp[i-1][j]); } } } cout<<dp[sa][sb]<<endl; return 0; }防卫导弹
#include<iostream> #include<cstring> using namespace std; int n; int a[200],dp[200]; int cmax=1; int main(){ cin>>n; while(n!=0){ cmax=1; memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++){ cin>>a[i]; dp[i]=1; } for(int i=1;i<n;i++){ for(int k=0;k<i;k++){ if(a[k]>=a[i]&&dp[k]+1>dp[i]){ dp[i]=dp[k]+1; } } if(dp[i]>cmax)cmax=dp[i]; } cout<<cmax<<endl; cin>>n; } return 0; }矩阵连乘积
#include<iostream> #include<cstring> using namespace std; int n; int dp[15][15]; int a[15][2]; int main(){ cin>>n; memset(dp,0x3f,sizeof(dp)); for(int i=1;i<=n;i++){ cin>>a[i][0]>>a[i][1]; dp[i][i]=0; } for(int i=1;i<=n;i++){ for(int j=1;j+i-1<=n;j++){ for(int k=j;k<j+i-1;k++){ if(dp[j][k]+dp[k+1][j+i-1]+a[j][0]*a[k][1]*a[j+i-1][1]<dp[j][j+i-1]){ dp[j][j+i-1]=dp[j][k]+dp[k+1][j+i-1]+a[j][0]*a[k][1]*a[j+i-1][1]; } } } } cout<<dp[1][n]<<endl; return 0; }田忌赛马
#include<iostream> #include<vector> #include<cstring> #include<algorithm> using namespace std; int n,ta,tb; vector<int> a,b; int dp[110][110]; bool cmp(int a,int b){ return a>b; } int main(){ cin>>n; while(n!=0){ memset(dp,0,sizeof(dp)); a.clear();b.clear(); for(int i=0;i<n;i++){ cin>>tb; b.push_back(tb); } for(int i=0;i<n;i++){ cin>>ta; a.push_back(ta); } sort(a.begin(),a.end(),cmp); sort(b.begin(),b.end(),cmp); for(int j=n-1;j>=0;j--){ for(int k=1;k<=n-j;k++){ if(a[j+k-1]<b[k-1]){ dp[j][k]=dp[j][k-1]+1; } else if(a[j+k-1]>b[k-1]){ dp[j][k]=dp[j+1][k-1]-1; } else if(a[j+k-1]==b[k-1]){ dp[j][k]=max(dp[j][k-1],dp[j+1][k-1]-1); } } } cout<<dp[0][n]<<endl; cin>>n; } return 0; }石子合并
#include<iostream> #include<cstring> using namespace std; int n,a[210],b[110],sum[110],cmin=9999999; int dp[110][110]; int main(){ cin>>n; while(n){ cmin=9999999; memset(a,0,sizeof(a)); for(int i=0;i<n;i++){ cin>>a[i]; a[i+n]=a[i]; } for(int i=0;i<n;i++){//枚举起点 memset(dp,0x3f,sizeof(dp)); memset(b,0,sizeof(b)); memset(sum,0,sizeof(sum)); sum[0]=b[0]=a[i]; for(int j=1;j<n;j++){ b[j]=a[i+j]; sum[j]=sum[j-1]+b[j]; } for(int j=0;j<n;j++){ dp[j][j]=0; } for(int l=2;l<=n;l++){ for(int x=0;x+l-1<n;x++){ for(int k=x;k<x+l-1;k++){ if(dp[x][k]+dp[k+1][x+l-1]+sum[x+l-1]-sum[x-1]<dp[x][x+l-1]) dp[x][x+l-1]=dp[x][k]+dp[k+1][x+l-1]+sum[x+l-1]-sum[x-1]; } } } if(cmin>dp[0][n-1])cmin=dp[0][n-1]; } cout<<cmin<<endl; cin>>n; } return 0; }旅游预算
#include<iostream> #include<iomanip> #include<vector> using namespace std; double Distance;//起点终点的距离 double tank;//车的油箱大小 double per_l_dis;//每升油可以走多远 double scost;//起点加油的价格 int n;//加油站的数目 struct station{ double dis;//距起点的距离 double cost;//每升油的价格 int next_station; }; station sts[55]; double dp[55];//从i号站点加满油到终点的最小花费 vector<int> v; int main(){ cin>>Distance>>tank>>per_l_dis>>scost; cin>>n; dp[0]=99999999; sts[0].dis=0; sts[n+1].dis=Distance; for(int i=1;i<=n;i++){ dp[i]=99999999; cin>>sts[i].dis>>sts[i].cost; //cout<<sts[i].dis<<' '<<sts[i].cost<<endl; } double longest=tank*per_l_dis;//加满油最远可以跑多少 for(int k=n;k>=0;k--){//枚举dp[k] if(sts[n+1].dis-sts[k].dis<=longest){ dp[k]=0;//直接可达到终点 sts[k].next_station=n+1; } else{ for(int i=k+1;i<=n;i++){//考察第k个加油站后面符合条件的加油站 if( ( sts[i].dis-sts[k].dis>=0.5*longest && sts[i].dis-sts[k].dis<=longest ) || ( sts[k].dis+longest<sts[i+1].dis && sts[k].dis+longest>=sts[i].dis ) ){ double ncost=(sts[i].dis-sts[k].dis)/per_l_dis*sts[i].cost; if(dp[i]+ncost<dp[k]){ dp[k]=dp[i]+ncost; sts[k].next_station=i; } } } } } int k=0; k=sts[k].next_station; while(k!=n+1){ v.push_back(k); k=sts[k].next_station; } cout<<fixed<<setprecision(2)<<dp[0]+scost+v.size()*2.0<<' '<<v.size()<<endl; for(int i=0;i<v.size();i++){ cout<<v[i]<<' '; } cout<<endl; return 0; }滑雪
#include<iostream> using namespace std; int m[110][110]; int c,r; int dp[110][110]; int visited[110][110]; int dx[4]={0,1,0,-1}; int dy[4]={-1,0,1,0}; int cmax=0; int f(int i,int j){ if(visited[i][j])return dp[i][j]; int flag=0;//标志为0，则四周不存在可以滑到的地方 for(int k=0;k<4;k++){ int x=i+dx[k],y=j+dy[k]; if(x>=0&&x<c &&y>=0&&y<r &&m[i][j]>m[x][y] &&dp[i][j]<f(x,y)+1){ flag=1; dp[i][j]=dp[x][y]+1; visited[i][j]=1; } } if(flag==0){ visited[i][j]=1; return dp[i][j]=1; } else{ return dp[i][j]; } } int main(){ cin>>c>>r; for(int i=0;i<c;i++){ for(int j=0;j<r;j++){ cin>>m[i][j]; } } for(int i=0;i<c;i++){ for(int j=0;j<r;j++){ if(cmax<f(i,j))cmax=dp[i][j]; } } cout<<cmax<<endl; return 0; }花生米（二）
#include<iostream> using namespace std; bool dp[1010]; int n; int main(){ cin>>n; dp[0]=dp[2]=dp[6]=dp[11]=dp[4]=dp[8]=dp[10]=1; dp[1]=dp[3]=dp[5]=dp[7]=dp[9]=0; for(int i=12;i<=1000;i++){ dp[i]=!(dp[i-1]&&dp[i-5]&&dp[i-10]); } while(n){ cout<<dp[n]<<endl; cin>>n; } return 0; }花生米（三）
#include<iostream> using namespace std; bool dp[1010][510]; int visited[1010][510]; int n; bool f(int i,int j){ //cout<<i<<" "<<j<<endl; if(i<0||i==1)return 0; if(visited[i][j])return dp[i][j]; if(i==0||i-1<=j){ visited[i][j]=1; return dp[i][j]=1; } int flag=0; for(int k=1;k<=j;k++){ if(f(i-k,k*2)==0){ flag=1; break; } } if(flag){ visited[i][j]=1; return dp[i][j]=1; } else{ visited[i][j]=1; return dp[i][j]=0; } } int main(){ cin>>n; while(n){ cout<<f(n,1)<<endl; cin>>n; } return 0; }花生米（四）
#include<iostream> using namespace std; int n; int a[15]; int main(){ cin>>n; while(n){ int sum=0; for(int i=0;i<n;i++){ cin>>a[i]; sum^=a[i]; } if(n%2==0){ if(sum)cout<<1<<endl; else cout<<0<<endl; } else{ if(sum)cout<<0<<endl; else cout<<1<<endl; } cin>>n; } return 0; }花生米（五）
#include<iostream> #include<cstring> using namespace std; double n; int m; int dp[10010];//表示杰瑞先手，在剩余j的情况下能胜否，如果是0就应该汤姆先手 int main(){ cin>>n; m=int(n*10); while(m>0){ memset(dp,0,sizeof(dp)); for(int j=0;j<=m-10;j++){//枚举剩余多少 int i=m-j;//i表示已经吃了多少 if(i>j)dp[j]=0;//面对这种情况不会胜利，把它留给汤姆 else if(3*i>=j)dp[j]=1;//这一次就可以吃完，这种好事当然杰瑞不会放过 else{ int flag=0; for(int k=i;k<=3*i;k++){//枚举所有的可能吃法 if(dp[j-k]==0){ //只要在这些可能中，至少有一种可以使得汤姆先手败，那么杰瑞照着k个先取，就能到达那一种状态 flag=1; break; } } if(flag)dp[j]=1; else dp[j]=0; } } cout<<!dp[m-10]<<endl;//dp[m-10]的意思是先取10个以后，下一个人先取胜否，与题目问的正好相反，所以取反 cin>>n; m=int(n*10); } return 0; }
