首页 > 代码库 > 小白书关于动态规划
小白书关于动态规划
10192 最长公共子序列
http://uva.onlinejudge.org/index.php?option=com_onlinejudge& Itemid=8&page=show_problem&category=114&problem=1133&mosmsg= Submission+received+with+ID+13297616
*/
#include <cstdio> #include <string.h> #include<istream> using namespace std; char s1[105],s2[105]; int dp[2][105]; int main() { int n,m,num=0; while(gets(s1)) { if(s1[0]==‘#‘) break; n=strlen(s1); gets(s2); m=strlen(s2); memset(dp,0,sizeof(dp)); int d=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) if(s1[i-1]==s2[j-1]) { dp[d][j]=dp[d^1][j-1]+1; } else dp[d][j]=dp[d][j-1]>dp[d^1][j]?dp[d][j-1]:dp[d^1][j]; d=d^1; } printf("Case #%d: you can visit at most %d cities.\n",++num,dp[d^1][m]); } return 0; }
147 这题输出的时候小心一点 就行 多重背包的方案数 */
#include <cstdio> #include <string.h> #include <iostream> #include<iomanip> using namespace std; int W[]={10000,5000,2000,1000,500,200,100,50,20,10,5}; long long dp[30005],num[30005]; int main() { char str[20]; while(true){ scanf("%s",str); int n=0; int L=1; int Len=strlen(str); while(Len!=0){ if(str[Len-1]!=‘.‘) { n+=(str[Len-1]-‘0‘)*L; L=L*10; } Len--; } if(n==0) break; memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=0;i<11;i++){ for(int j=W[i];j<=n;j++) dp[j]=dp[j]+dp[j-W[i]]; } printf("%6s",str); cout<<setw(17)<<dp[n]<<endl; } return 0; }
/* uva 357 简单 硬币划分种类 还是 long long 的 数值没搞好 记住数值预测 */
#include <cstdio> #include <string.h> #include <iostream> using namespace std; long long dp[30005]; int W[]={1,5,10,25,50}; int main(){ memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=0;i<5;i++){ for(int j=W[i];j<=30000;j++) dp[j]=dp[j-W[i]]+dp[j]; } int n; while(scanf("%d",&n)==1){ if(dp[n]!=1) cout<<"There are "<<dp[n]<<" ways to produce "<<n<<" cents change."; else cout<<"There is only 1 way to produce "<<n<<" cents change."; cout<<endl; } return 0; }
/* uva 526 题目说的是 有一堆硬币 然后 让面值 尽量均分给两个人 可以先假设 首先将这些硬币全部给
一个人 然后 将每个面值 乘 2 变为负数，这样就能够 将他看成是 01背包 就是说，像这样
每个物品如果转移 那么就会 产生 2*W 的逆差 就这样 不断的去找就能找到 最小的结果 dp[j]=dp[j-w[i]]; */
#include <cstdio> #include <string.h> #include <iostream> using namespace std; bool dp[100005]; int w[105]; int main(){ int T; scanf("%d",&T); while(T--){ int m,i,a,sum=0; scanf("%d",&m); for(i=0;i<m;i++){ scanf("%d",&a); w[i]=-a*2; sum+=a; } int mmm=sum; memset(dp,false,sizeof(dp)); dp[sum]=true; for( i=0;i<m;i++) for(int j=0;j<sum;j++) if(dp[j-w[i]]){ dp[j]=true; if(mmm>j)mmm=j; } printf("%d\n",mmm); } return 0; }
/* uva 348 矩阵连乘 写出计算的方程式 小白书上提示了这题该怎么做自然很容易就 可以得到 了状态转移方程dp[i][j]=min(dp[i][j]#dp[j+1][i+k])然后计入每个状态是从哪里来的 就 好了*/
#include <cstdio> #include<iostream> #include <string.h> using namespace std; struct point{ int LX,LY,RX,RY; point(int a=0,int b=0,int c=0,int d=0) { LX=a;LY=b;RX=c;RY=d; } }di[15][15]; struct node { int X,Y; int num; node(int a=0,int b=0,int c=0) { num=a;X=b;Y=c; } }dp[15][15]; void dfs(int a,int b) { if(a==b) { printf("A%d",a); return ; } printf("("); dfs(di[a][b].LX,di[a][b].LY); printf(" x "); dfs(di[a][b].RX,di[a][b].RY); printf(")"); } int main(){ int n,mmm=0; while(true){ scanf("%d",&n); if(n==0)break; int j,i,k,h; for(i=1;i<=n;i++){ int a,b; scanf("%d%d",&a,&b); dp[i][i]=node(0,a,b); } for(i=1;i<n;i++){ int num=dp[i][i].X*dp[i+1][i+1].Y*dp[i][i].Y; dp[i][i+1]=node(num,dp[i][i].X,dp[i+1][i+1].Y); di[i][i+1]=point(i,i,i+1,i+1); } for( k=2;k<=n;k++) for( i=1;i+k<=n;i++) { dp[i][i+k].num=2147483647; for(j=i;j<i+k;j++){ int num=dp[i][j].X*dp[j+1][i+k].Y*dp[i][j].Y+dp[i][j].num+dp[j+1][i+k].num; if(dp[i][i+k].num>num){ dp[i][i+k]=node(num,dp[i][j].X,dp[j+1][i+k].Y); di[i][i+k]=point(i,j,j+1,i+k); } } } printf("Case %d: ",++mmm); printf("("); dfs(di[1][n].LX,di[1][n].LY); printf(" x "); dfs(di[1][n].RX,di[1][n].RY); printf(")\n"); } return 0; }
/* uva 624 CD 01 背包 然后打印方案总数，选取最大的 容量 背包所能承受的 我用了二维的数组来存储 路径 */
#include <cstdio> #include <string.h> #include <iostream> using namespace std; bool dp[25][10000]; bool per[25][10000]; int w[25]; int main() { int n; while(scanf("%d",&n)==1){ memset(per,false,sizeof(per)); memset(dp,false,sizeof(dp)); int i,j,k,max_v=0,m; scanf("%d",&m); for(i=1;i<=m;i++) scanf("%d",&w[i]); dp[m+1][0]=true; for(i=m;i>0;i--) for(j=0;j<=n;j++) { dp[i][j]=dp[i+1][j]; if(j>=w[i]&&dp[i+1][j-w[i]]){ if(j>max_v)max_v=j; per[i][j]=true; dp[i][j]=true; } } k=max_v; for(i=1;i<=m;i++) if(per[i][k]){ printf("%d ",w[i]); k=k-w[i]; } printf("sum:%d\n",max_v); } return 0; }
/* 10130 多个的 01 背包 混在 一起 刚开始读错题了 以为每件商品只能选一次 坑了 看来自己 还得继续 努力啊 ！ */
#include<cstdio> #include<string.h> #include<iostream> using namespace std; int w[1005],c[1005],g[105],dp[35]; int main(){ int t; cin>>t; while(t--){ int n,m; cin>>n; for(int i=0;i<n;i++) cin>>w[i]>>c[i]; cin>>m; for(int i=0;i<m;i++) cin>>g[i]; int ans=0,maxv=0; for(int k=0;k<m;k++){ for(int i=1;i<=g[k];i++) dp[i]=-1; dp[0]=0; maxv=0; for(int i=0;i<n;i++) for(int j=g[k];j>=c[i];j--) if(dp[j-c[i]]!=-1&&dp[j]<dp[j-c[i]]+w[i]){ dp[j]=dp[j-c[i]]+w[i]; if(dp[j]>maxv) maxv=dp[j]; } ans+=maxv; } cout<<ans<<endl; } return 0; }
/* 最长公共子序列 输出路径 lcs 加上路径输出 */
#include<cstdio> #include<iostream> #include<string.h> using namespace std; const int maxn=105; const int maxm=35; char str1[maxn][maxm]; char str2[maxn][maxm]; char ch[maxn][maxn]; int dp[maxn][maxn]; void print(int a,int b,int g){ if(a==0||b==0) return ; if(ch[a][b]==‘c‘){ int c=g; g=1; print(a-1,b-1,g); if(c==0) printf("%s\n",str1[a-1]); else printf("%s ",str1[a-1]); } else { if(ch[a][b]==‘L‘) print(a,b-1,g); else print(a-1,b,g); } } int main() { int i,j,n=0,m=0; while(scanf("%s",str1[0])==1){ n=0;m=0; memset(ch,0,sizeof(ch)); memset(dp,0,sizeof(dp)); while(str1[n][0]!=‘#‘){ scanf("%s",str1[++n]); } while(true){ scanf("%s",str2[m]); if(str2[m][0]==‘#‘) break; ++m; } for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(strcmp(str1[i-1],str2[j-1])==0){ dp[i][j]=dp[i-1][j-1]+1; ch[i][j]=‘c‘; }else{ if(dp[i][j-1]>dp[i-1][j]) { dp[i][j]=dp[i][j-1]; ch[i][j]=‘L‘;} else { dp[i][j]=dp[i-1][j];ch[i][j]=‘U‘; } } print(n,m,0); } return 0; }
/* uva 10456 简单的完全背包问题 */
#include <cstdio> #include <string.h> #include <iostream> using namespace std; const int maxn=10005; int dp[maxn]; bool mark[maxn]; int main(){ int a[2],t; while(scanf("%d%d%d",&a[0],&a[1],&t)==3){ int i,j; memset(mark,false,sizeof(mark)); mark[0]=true; memset(dp,0,sizeof(dp)); for(i=0;i<2;i++) for(j=a[i];j<=t;j++) if(mark[j-a[i]]&&dp[j]<dp[j-a[i]]+1){ dp[j]=dp[j-a[i]]+1; mark[j]=true; } for(i=t;i>=0;i--) if(mark[i]){ if(i==t) printf("%d\n",dp[i]); else printf("%d %d\n",dp[i],t-i); break; } } return 0; }
/* uva 10258 这都能A 不敢爱了 R*C*R*C的时间效率 这题说的是
在滑雪的时候 选择 最长的下坡路 然后 可以向周边的 四个地方 划过去
让后就顺利 解决了 即 dp[i+x][j+y]=max(dp[i][j]+1); 进行 R*C次的迭代 */
#include<cstdio> #include<string.h> #include<iostream> using namespace std; const int maxn=105; char str[1000]; int dp[maxn][maxn]; int map[maxn][maxn]; int xx[]={1,-1,0,0}; int yy[]={0,0,1,-1}; int main() { int t; scanf("%d",&t); while(t--){ memset(dp,0,sizeof(dp)); int R,C,i,j,k,maxv=0; scanf("%s%d%d",str,&R,&C); for(i=0;i<R;i++) for(j=0;j<C;j++){ scanf("%d",&map[i][j]); dp[i][j]=1; } for(k=0;k<R*C;k++){ bool flag=true; for(i=0;i<R;i++) for(j=0;j<C;j++){ for(int h=0;h<4;h++){ int x=xx[h]+i,y=yy[h]+j; if(x>=0&&x<R&&y>=0&&y<C&&dp[x][y]<(dp[i][j]+1)&&map[x][y]<map[i][j]){ dp[x][y]=dp[i][j]+1; flag=false; if(dp[x][y]>maxv) maxv=dp[x][y]; } } } if(flag) break; } printf("%s: %d\n",str,maxv); } return 0; }
/* 记忆化搜索 他说的是有很多的 长方体 小的放上面 让 最大高度 做出 每种可能出现的面 */
#include<cstdio> #include<string.h> #include<iostream> using namespace std; const int maxn=205; struct point{ int x,y,z; point (int a=0,int b=0,int c=0){ x=a;y=b;z=c; } }T[maxn]; int num,n,maxv,dp[maxn]; int dfs(int a) { if(dp[a]) return dp[a]; dp[a]=T[a].z; for(int i=0;i<num;i++) if(T[i].x<T[a].x&&T[i].y<T[a].y){ int temp=dfs(i)+T[a].z; if(temp>dp[a]) dp[a]=temp; } if(dp[a]>maxv) maxv=dp[a]; return dp[a]; } int main() { int tt=0; while(scanf("%d",&n)==1){ if(n==0) break; int i; num=0; maxv=0; memset(dp,0,sizeof(dp)); for(i=0;i<n;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); T[num++]=point(x,y,z); T[num++]=point(y,x,z); T[num++]=point(y,z,x); T[num++]=point(z,y,x); T[num++]=point(z,x,y); T[num++]=point(x,z,y); } for(i=0;i<num;i++) dfs(i); printf("Case %d: maximum height = %d\n",++tt,maxv); } return 0; }
/*
这题 想到动态转移方程 即dp[i]所能到达的地方状态 一旦全为 必胜的 状态 这就必败了
这个点能到的 状态 只要有 一个是 必败的状态那么 这个点就是必胜的
dp[0]=false;
0 时是必败的对于先手来说 然后就可以转移方程了
这样就有动态方程 dp[i]|=dp[i-A[j]];
#include<cstdio> #include<string.h> #include<iostream> using namespace std; int n,m,A[11]; bool w[1000005]; int main() { int i,j; while(scanf("%d",&n)==1){ scanf("%d",&m); for(i=0;i<m;i++) scanf("%d",&A[i]); w[0]=false; for(i=1;i<=n;i++) { w[i]=false; for(j=0;j<m;j++) w[i]|=A[j]<=i&&!w[i-A[j]]; } if(w[n]) printf("Stan wins\n"); else printf("Ollie wins\n"); } return 0; }
/* 题目的 意思是 给定你一个字符串判断字符串正所处的状态
simple stage O = A
fully-grown stage O = OAB
mutagenic stage O = BOA
可能进行多次的嵌套
然后 用dp进行处理 经过分析可以很清楚的知道 状态的 转移只有两种
要么是第二种要么是第三种 当然只有一个的时候。 可能是第一种，然
后就得到这样的状态转移到方程
dp[i][j+i]=work(dp[j+1][j+i])
dp[j][j+i]=work(dp[j+1][j+i-1])
由题目所述 前者优先 */
#include<cstdio> #include<string.h> #include<iostream> using namespace std; int dp[1000][1000]; char str[1050]; int main(){ int n; scanf("%d",&n); getchar(); while(n--){ gets(str); int Len=strlen(str); for(int i=0;i<Len;i++) for(int j=0;j<Len;j++) dp[i][j]=0; for(int i=0;i<Len;i++) if(str[i]==‘A‘) dp[i][i]=1; for(int i=2;i<=Len;i++) for(int j=0;j+i<Len;j++){ if(str[j+i]==‘B‘&&str[j+i-1]==‘A‘&&dp[j][j+i-2]){ dp[j][j+i]=2; continue; } if(str[j]==‘B‘&&str[j+i]==‘A‘&&dp[j+1][j+i-1]){ dp[j][j+i]=3; } } int g=dp[0][Len-1]; if(g==1) { printf("SIMPLE\n"); continue; } if(g==2){ printf("FULLY-GROWN\n"); continue; } if(g==3){ printf("MUTAGENIC\n"); continue; } printf("MUTANT\n"); } return 0; }
#include<cstdio>/* 825 应该是求背包的 种类 一个spaf 就可以了*/ #include<string.h> #include<iostream> #include<queue> using namespace std; const int maxn=105; const int maxv=2147483647; struct node{ int x,y; node (int a=0,int b=0) { x=a;y=b; } }; int N[maxn][maxn],M[maxn][maxn]; bool mark[maxn][maxn],inq[maxn][maxn]; int n,m; char str[maxn]; int xx[]={-1,1,0,0}; int yy[]={0,0,-1,1}; int main(){ int tt=0; scanf("%d",&tt); while(tt--){ queue<node>Q; scanf("%d%d",&n,&m); getchar(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ mark[i][j]=false; M[i][j]=maxv; N[i][j]=0; inq[i][j]=false; } for(int i=1;i<=n;i++){ gets(str); int Len=1,L=0; while(Len<=strlen(str)){ if(str[Len]>=‘0‘&&str[Len]<=‘9‘){ L=L*10+str[Len]-‘0‘; } else { if(L!=0) mark[i][L]=true; L=0; } Len++; } } node t; N[1][1]=1; M[1][1]=0; Q.push(node(1,1)); inq[t.x][t.y]=true; while(!Q.empty()){ t=Q.front(); Q.pop(); if(mark[t.x][t.y]) continue; inq[t.x][t.y]=false; for(int i=0;i<4;i++){ int x=t.x+xx[i],y=t.y+yy[i]; if(x<1||x>n||y<1||y>m||mark[x][y]) continue; if(M[x][y]<M[t.x][t.y]+1)continue; if(M[x][y]==M[t.x][t.y]+1){ N[x][y]+=N[t.x][t.y]; } else N[x][y]=N[t.x][t.y]; M[x][y]=M[t.x][t.y]+1; if(!inq[x][y]) { inq[x][y]=true; Q.push(node(x,y)); } } } printf("%d\n",N[n][m]); if(tt!=0) printf("\n"); } return 0; }
/*
这题说的是在一个母串中存在一个子序列的个数
例如
babgbag
bag
5个
可以很清楚的知道字母之间的联系只与前或者后有关系
然后可以知道 dp[i]+=local(dp[i-1]);强大的剪枝
*/
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int maxn=10000000; const int tap=10002; int dp[10005][40],Len[10005]; char s1[10005],s2[105]; void add(int L,int R){ int G=0,i; for(i=0;i<Len[L];i++){ G=(dp[L][i]+dp[R][i]+G); dp[R][i]=G%maxn; G=G/maxn; } while(G!=0){ G=(G+dp[R][i]); dp[R][i]=G%maxn; i++; G=G/maxn; } if(Len[R]<i)Len[R]=i; } void copydate(int L,int R){ memset(dp[L],0,sizeof(dp[L]));Len[L]=0; for(int i=0;i<Len[R];i++) dp[L][i]=dp[R][i]; Len[L]=Len[R]; } int main() { int t; scanf("%d",&t); while(t--){ scanf("%s%s",s1,s2); int L1=strlen(s1),L2=strlen(s2); memset(Len,0,sizeof(Len)); memset(dp,0,sizeof(dp)); for(int i=0;i<L1;i++) if(s1[i]==s2[0])dp[i][Len[i]++]=1; for(int i=1;i<L2;i++){ memset(dp[tap],0,sizeof(dp[tap]));Len[tap]=0; for(int j=0;j<L1;j++){ bool flag=true; if(s2[i]==s1[j]&&Len[tap]!=0){ copydate(tap+1,j); copydate(j,tap); flag=false; } if(Len[j]!=0&&flag) { add(j,tap); memset(dp[j],0,sizeof(dp[j]));Len[j]=0; } if(!flag&&Len[tap+1]!=0){ add(tap+1,tap);memset(dp[tap+1],0,sizeof(dp[tap+1]));Len[tap+1]=0; } } } memset(dp[tap],0,sizeof(dp[tap])); Len[tap]=0; for(int i=0;i<L1;i++) if(Len[i]!=0)add(i,tap); while(dp[tap][Len[tap]-1]==0&&Len[tap]>1) Len[tap]--; printf("%d",dp[tap][Len[tap]-1]);Len[tap]--; while(Len[tap]>=1){ printf("%07d",dp[tap][Len[tap]-1]);Len[tap]--;} printf("\n"); } return 0; }
uva10534 这题说的是找一个序列 左 边 严 格 递 增 右 边 严 格 递 减 然 后 左边的个数和 右边的个数 要相同 保证左边的个数为 N 右 边 的 个 数也为N总公 N*2+1 个
我用了 两次 二分的LIC 正向 一次 反向一次 然后枚举区间的值
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int maxn=10005; int dp[2][maxn]; int M[2][maxn],T[maxn]; int birseach(int n,int w){ int L=0,R=n-1,mid; while(L<R){ mid=L+(R-L)/2; if(T[mid]==w) return mid; if(w>T[mid]) L=mid+1; else R=mid-1; } if(T[L]<w)L++; return L; } void LIS(int n,int h){ int Len=1; T[0]=M[h][0]; dp[h][0]=1; for(int i=1;i<n;i++){ if(M[h][i]>T[Len-1]){ T[Len++]=M[h][i]; } else { int in=birseach(Len,M[h][i]); T[in]=M[h][i]; } dp[h][i]=Len; } } int main() { int n; while(scanf("%d",&n)==1){ for(int i=0;i<n;i++){ scanf("%d",&M[0][i]); M[1][n-1-i]=M[0][i]; } LIS(n,0); LIS(n,1); int ma=0; for(int i=0;i<n;i++){ int L=dp[0][i]<dp[1][n-1-i]?dp[0][i]:dp[1][n-1-i]; if(ma<L)ma=L; } printf("%d\n",(ma-1)*2+1); } return 0; }
uva10651 这题说的是给了一串‘_‘、‘ o‘ 组成的 字符串 看几组数据个吧就更好理解了
5
---oo------- 1
-o--o-oo---- 2
-o----ooo---
就是说连起来的 三个字符 中间一个必须为‘o‘ 然后 如果左边为 ‘o’ 那么右边 必须为‘_’ 然后如果 左边的 那个移到右边去 那么中间的 那个就消掉 从 oo_ 变成__o
反方向就是 _oo 变成 o__ 然后 尽可能的消掉‘o’ 计算最少剩下几个没有被消掉
看看 字符串规定为12 然后就 不超过5000种的状态 然后 先处理好他们的 转换关系 然后每个一个串 转化为一个值 然后进行一次最长路
#include <iostream> #include<string.h> #include<cstdio> #include<vector> #include<queue> using namespace std; const int maxn=5000; vector<int>P[maxn]; int dis[maxn]; bool inq[maxn]; int main() { char str[15]; for(int i=0;i<(1<<12);i++){ int d=i; for(int j=2;j<12;j++){ if((d&(1<<(j-1)))&&(d&(1<<j))&&(d&(1<<(j-2)))==0) P[d].push_back(d^(1<<(j-1))^(1<<j)^(1<<(j-2))); if((d&(1<<(j-1)))&&(d&(1<<(j-2)))&&(d&(1<<j))==0) P[d].push_back(d^(1<<(j-1))^(1<<j)^(1<<(j-2))); } } int t; scanf("%d",&t); while(t--){ memset(dis,0,sizeof(dis)); memset(inq,false,sizeof(inq)); scanf("%s",str); int L=0,ma=0,num=0; for(int i=0;i<12;i++){ if(str[i]==‘o‘) { L=L*2+1; ++num; } else L=L*2; } dis[L]=0; queue<int>Q; Q.push(L); while(!Q.empty()){ int x=Q.front(); Q.pop(); if(dis[x]>ma) ma=dis[x]; inq[x]=false; for(int i=0;i<P[x].size();i++){ int to=P[x][i]; if(dis[to]<dis[x]+1){ dis[to]=dis[x]+1; if(!inq[to]){ inq[to]=true; Q.push(to); } } } } printf("%d\n",num-ma); } return 0; }
uva 10051 这题说的是 有n个正方体 每个正方体的每一面都有以一种颜色 要将这些正方体堆叠起来 堆叠的要求
1 重量小的不能放在重量大的上面
2 在他们的面与面的连接处应该有相同的颜色。
题目给的正方体 是按照重量递增给的然后计算给了n个正方体 计算最多能够堆叠几个正方体
对于这题可以将他转化为最长递增子序列 讲一个正方体变成6个点 这六个点的重量相同既不会同时出现一个正方体被用了两次
每个点都对应于一个面 相同就从与他^1的点出来应为这是对面的点
dp[i]=max(dp[j^1]+1)
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int maxn=500*6+50; int per[maxn],dp[maxn],color[maxn],F[maxn]; char str[][10]={ {"front"},{"back"},{"left"},{"right"},{"top"},{"bottom"} }; int main() { int t=0,n; while(scanf("%d",&n)==1){ int k=0; if(n==0) break; if(t!=0) printf("\n");t++; k=n*6; for(int i=1;i<=n;i++){ k=k-6; for(int j=0;j<6;j++){ scanf("%d",&color[k+j]); F[k+j]=i; } } int mav=0,loc; memset(dp,0,sizeof(dp)); memset(per,-1,sizeof(per)); for(int i=0;i<n*6;i++){ dp[i]=1; for(int j=0;j<i;j++) if(color[j]==color[i]&&F[j]>F[i]&&dp[i]<dp[j^1]+1){ dp[i]=dp[j^1]+1; per[i]=j; } if(dp[i]>mav){ mav=dp[i];loc=i;} } printf("Case #%d\n%d\n",t,mav); loc=loc^1; while(loc!=-1){ int G=loc%6; printf("%d %s\n",F[loc],str[G]); loc=loc^1; loc=per[loc]; } } return 0; }
uva 590 说的是 一个人为了逃避警察的追捕 然后从1这个点每天坐一趟飞机 第k天 必须到达 n点的 最小费用
dp[i][k]=min(dp[i][k],dp[i][k-1]+cost);
#include <iostream> #include<string.h> #include<cstdio> using namespace std; const int maxn=15; const int maxm=1005; const int maxv=2147483647; int edg[maxn][maxn][35]; int Len[maxn][maxn]; int dp[maxn][maxm]; int main() { int cas=0; while(true){ int n,m; scanf("%d%d",&n,&m); if(n==0&&m==0) break; for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j]=maxv; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ Len[i][j]=1; if(i==j){ edg[i][j][0]=0; continue; } int num; scanf("%d",&num); Len[i][j]=num; for(int k=0;k<num;k++) scanf("%d",& edg[i][j][k]); } dp[1][0]=0; for(int k=1;k<=m;k++) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j){ if(i==j) continue; int L=Len[j][i]; int cost=edg[j][i][(k-1)%L]; if(cost==0||dp[j][k-1]==maxv) continue; dp[i][k]=dp[i][k]>dp[j][k-1]+cost?dp[j][k-1]+cost:dp[i][k]; } printf("Scenario #%d\n",++cas); if(dp[n][m]==maxv) printf("No flight possible.\n"); else printf("The best flight costs %d.\n",dp[n][m]); printf("\n"); } return 0; }
uva 10306 这 题 说 的 是 给 了 一 种 钱 币 是 有 两 种 价 值 构 成 的 这 种 钱 币 叫 做 e-coin(E,H) 然 后 这 种 钱币换成 M=sqrt(E*E+H*H)价 值 的 T 钱 币
然 后 转 化 为 求背包的最小件数
dp[i+W[0][k]][W[1][k]]=min(dp[i][j]+1)
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int maxn=305; const int maxm=45; const int maxv=2147483647; int W[2][maxm],dp[maxn][maxn]; int main() { int t; scanf("%d",&t); while(t--){ int m,S; scanf("%d%d",&m,&S); int G=S*S; for(int i=0;i<=S;i++) for(int j=0;j<=S;j++) dp[i][j]=maxv; int ma=maxv; for(int i=0;i<m;i++) scanf("%d%d",&W[0][i],&W[1][i]); dp[0][0]=0; for(int k=0;k<m;k++) for(int i=0;i<=S;i++){ int H=W[0][k]+i; if((H)*(H)+W[1][k]*W[1][k]>G) break; for(int j=0;;j++){ int F=j+W[1][k]; if(H*H+F*F>G)break; if(dp[i][j]==maxv) continue; dp[H][F]=dp[i][j]+1>dp[H][F]?dp[F][H]:dp[i][j]+1; if(H*H+F*F==G)ma=ma>dp[H][F]?dp[H][F]:ma; } } if(ma==maxv) printf("not possible\n"); else printf("%d\n",ma); } return 0; }
uva 10739 题目说的是给定 一个字符串 你可以进行下列三种的运算
1 在任何位置增加一个字符
2 在任何位置替换某个字符
3 在任何位置删除某个字符
转移方程 当str[i]==str[j]相等的时候 dp[i][j]=dp[i-1][j-1]
还有 dp[i][j]=min(dp[i][j],dp[i+1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1) (dp[i+1][j]+1,dp[i][j-1]+1)增加 一个字符 dp[i-1][j-1]+1 是 替 换 一 个 字符 对 于删 除 可以和增加类似
#include <iostream> #include <cstdio> #include <string.h> using namespace std; const int maxn=1005; const int maxv=2147483647; char str[maxn]; int dp[maxn][maxn]; int minv(int a,int b){ return a<b?a:b; } int main() { int t; scanf("%d",&t); for(int cas=1;cas<=t;cas++){ scanf("%s",str); int Len=strlen(str); for(int i=0;i<Len-1;i++){ dp[i][i]=dp[i+1][i+1]=0; if(str[i]==str[i+1])dp[i][i+1]=0; else dp[i][i+1]=1; } for(int k=2;k<Len;k++) for(int i=0;i+k<Len;i++){ int j=i+k; dp[i][i+k]=maxv; if(str[i]==str[j])dp[i][j]=dp[i+1][j-1]; dp[i][j]=minv(minv(dp[i][j],minv(dp[i+1][j]+1,dp[i][j-1]+1)),dp[i+1][j-1]+1); } printf("Case %d: %d\n",cas,dp[0][Len-1]); } return 0; }
uva 10304 这题说的是 给了e1 e2 e3 e4 e5 ... 值 是 严 格 递 增 也就是说 给 了 一 个 效 率 最 差 的 查 找 二 叉 树(按 照 查 找 二 叉 树 的 建 树 规 则 是 这 样 的 当 一 个 结 点 大于它的 父亲节点那么他就放在该父亲节点的 右 子 树 上 如果小于 就放在左子树上等于的话就看自己怎么设置这课树了，(呵呵 数据结构的课程设计就是做这个 理解起来就相对容易些)) 然 后 给了 对于每个点 都有被找到的次数 和离根节点的 距离 分别是 f[x] 和 cost[x] 然后计算
f(e1)*cost(e1) + f(e2)*cost(e2) + ... + f(en)*cost(en) 使得这个值最小(也就是使得这课二叉查找树的效率达到最佳)
可以知道 排序二叉树 左孩子的 值一定小于根节点 右孩子的值大于 根节点 通过改变根节点可以使得这课树达到最佳的状态
接下来就是处理根节点的问题了 可以想象一下 当这棵树只有 2个节点 的时候 要达到最优的树 可以通过枚举 根结点 然后三个节点的树呢 是不是可以通过 枚举三个节点中任意一个节点作为 根节点 与其余两个节点所能得到最优树 配合达到最优的树得到的解呢 可以想象一下 这三个节点在枚举的时候已经能够将这颗树的所有情况考虑在内了 ，现在这样想想 是不是 最优子结构呢？ 好像有点道理 就是最优子结构 没有任何的后效性 ，
dp[i][j] 表示 节点 i到j 为节点 所能得到的最优树 那么 这样的方程又会由什么样的状态转移而来呢 刚刚咱们上面说了 最优子结构 然后枚举 根节点
得到 dp[i][j]=dp[i][k-1]+w[i][k-1]+dp[k+1][j]+w[k+1][j] 可以知道这整棵树都向下移动了一个距离就是 加上这正整棵树的权值
视乎到这里 已经得了解
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int maxn=255; const int maxv=2147483647; int dp[maxn][maxn]; int w[maxn][maxn]; int minv(int a,int b){ return a>b?b:a; } int main() { int n; while(scanf("%d",&n)==1){ memset(dp,0,sizeof(dp)); memset(w,0,sizeof(w)); for(int i=1;i<=n;i++) scanf("%d",&w[i][i]); for(int k=1;k<n;k++) for(int i=1;i+k<=n;i++){ w[i][i+k]=w[i][i+k-1]+w[i+k][i+k]; dp[i][i+k]=maxv; } for(int t=0;t<n;t++) for(int i=1;i+t<=n;i++){ int j=i+t; for(int k=i;k<=j;k++) { dp[i][j]=minv(dp[i][j],dp[i][k-1]+w[i][k-1]+dp[k+1][j]+w[k+1][j]); } } printf("%d\n",dp[1][n]); } return 0; }
uva 1207 佳佳的筷子 这题说的是 佳佳 请客吃饭 总共 k+8个人 有n 支筷子 然后每个人有三支筷子 然后 每次选定三跟筷子都是 （假设这里的 较小的两根筷子叫做 A，B）计算使得拿出k+8双筷子后 每个配合的 （A+B）*（A+B） 的总和最小 表示没有想出来 经过提醒 考虑第 j 根筷子选还是不选 这样就有 前 j 根筷子 选出 i 个 集 合筷子的方法有多少种 dp[i][j]
我们可以推得 如果选了第 j 根 那么 他 用 的 就 是 和 j-1 个 搭 配 如果选了 第j+1 根筷子就和 第 j 根 搭 配 那 么 这 样 我 们 就 把 所 有 的 情 况 考 虑 在 内 了， 然 后 可 以 知 道 动 态方程 dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+(w[j]*w[i-1])*(w[j]*w[i-1])); 记 得 将 个 序 列 倒 置 这 样 就 解 决 了 选出一根较长的 问题 ，倒序的话 就可以很容易的控制边界问题 使得一定选的较长的 在前面也就是 较大的那个 可以通过控制边界到达 可以知道 选dp[1][j] 的起始点必须是 从第3根筷子开始的（当然这里说的是倒叙后的） dp[2][j]的边界自然是从 第6根开始的 那这样 像dp[1][2-1] =INF dp[2][5]=INF 因为他是 不 可 能 取 到 的 好 现在就 放在规划好的方程中去算吧
自己的思考 脑残的是这样想的 dp[i][j][k]; 在区间 i j 之间算出 k个组合的筷子的最小 费用 额 发现时间爆空间爆 额 好吧 但是却没有去考虑 第 j 根 筷子有没有选 前 j根筷子 挑出了几个组合
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int maxn=1010; const int maxv=2147483647; int dp[maxn][maxn*5]; int w[maxn*5]; int minv(int a,int b){ return a<b?a:b; } int main() { int t; scanf("%d",&t); while(t--){ int k,n; scanf("%d%d",&k,&n); for(int i=0;i<n;++i) scanf("%d",&w[i]); k=k+8; for(int i=0;i<n/2;i++){ dp[0][i]=0; int t=w[i]; w[i]=w[n-i-1]; w[n-i-1]=t; dp[0][n-i-1]=0; } for(int i=1;i<=k;i++){ for(int j=0;j<n;j++){ if(j<(i-1)*3+2) dp[i][j]=maxv; else dp[i][j]=minv(dp[i][j-1],dp[i-1][j-2]+(w[j-1]-w[j])*(w[j-1]-w[j])); } } printf("%d\n",dp[k][n-1]); } return 0; }
uva 10617这题说的是 给了一个长度不大于60的字符串然后你可以任意的删除字符 使得这个字符串为回文串 当然回文串的长度是大于等于1的 然后现在来找到其中的规律
起初我们在想对于这个问题与回文串是否有关系 然后就按照回文串的思路去想了 当在某个较小的区间内 dp[i][j] 要使得这个串 i 到 j 为回文串 那么得有几种方法 首先 str[i] 被去掉 那么dp[i][j] 就等于dp[i+1][j] 如果j被去掉了 那么dp[i][j]=dp[i][j-1] 那么dp[i][j]=dp[i+1][j]+dp[i][j-1]; 视乎我们多做了一些东西 就是dp[i+1][j]里面包含了dp[i+1][j-1] 且dp[i][j-1]里面也包含了 dp[i+1][j-1]那 这样就重复算了 当然结果记得 减去dp[i+1][j-1] 还有当 str[i]==sti[j]的时候呢 是不是我们就多了dp[i+1][j-1]种方法就上将里面的全部都删了 就是增加了dp[i+1][j-1]+1
总结一下 我们就得到了 dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1] 如果str[i]==str[j] dp[i][j]+=dp[i+1][j-1]+1; 这里的 个数超过了int wa 在这里一次了
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int maxn=65; long long dp[65][65]; int main() { int t; char str[maxn]; scanf("%d",&t); while(t--){ memset(dp,0,sizeof(dp)); scanf("%s",str); int len=strlen(str); for(int i=1;i<=len;++i) dp[i][i]=1; for(int i=1;i<len;i++) for(int j=1;j+i<=len;j++){ dp[j][j+i]=dp[j+1][j+i]+dp[j][j+i-1]-dp[j+1][j+i-1]; if(str[j-1]==str[j+i-1]) dp[j][i+j]+=1+dp[j+1][j+i-1]; } printf("%lld\n",dp[1][len]); } return 0; }
uva11137 这题说的是 有一种 货币 单位价值分别是 1 8 27 .. 21*21*21 就是 1到 21的 各 个 数 三 次 方 的 然后给了一个价值看能够拼成这个价值的种类有多少种
完全背包 dp[j]+=dp[j-w[i]] 这样就拼得了价值为n的 物品的总方案数
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int maxn=10005; int w[22]; long long dp[maxn]; int main() { for(int i=1;i<=21;++i) w[i-1]=i*i*i; int n; while(scanf("%d",&n)==1){ memset(dp,-1,sizeof(dp)); dp[0]=1; for(int i=0;i<21;i++){ for(int j=w[i];j<=n;j++) if(dp[j-w[i]]!=-1){ dp[j]=dp[j]==-1?dp[j-w[i]]:dp[j]+dp[j-w[i]]; } } printf("%lld\n",dp[n]); } return 0; }
uva 这题说的是 有最多5607 只乌龟 每只乌龟有自己的重量和承重能力 例如 一个人他有 重量为 200 那么他的承重能力是 1000 那么在他的背上就还可以堆重量为800的 东西 然后计算最多可以将乌龟堆得最高
首先考虑 如果乌龟的 cap-weight 比较大 那么他就能够承载的比较多 因 此 他 就 比 较 有 可 能 放 在 比 较 下 面 发 现 这 样 的 猜 想 是 正 确 的
dp[i][len[j]+1]=min(dp[i][len[j]+1],min(dp[j][len[j]]-T[i].w,T[i].cap)) 在不知道 体重和力量最大值的情况下我就用这种方法作了 但是还是过了 可能是数据比较水 这显然不是正确的时间复杂度
正解应该是这样的
首先 将这些乌龟按照 力量值进行排序 按从小到达的顺序排列 为什么这样 假设 两只 乌龟的力量和重量分别是 s1 w1 s2 w2 如果s2》 s1 假设 s1
能够将 两只乌龟 抬起来 那么就有 s1>w1+w2 此时 可以肯定的是 在后面的 堆叠当中所能承载的 乌龟 要比 s2 在下面来得更小很多 当s2 大于w1+w2 的时候 s1 并不一定能够大于w1+w2 那么就证明如果可以堆起来 那么力量大的一定能够放在比较下面 如果他在 这个最长的堆叠当中的话
那么 此时的 dp[i][j] 表示堆到 i的高度的时候前j个最小重量 由于5607 过于强大 那么现在就用滚动数组进行处理 dp[h]=min(dp[h-1]+w[i],dp[h]) 这里要记得是从后面的高度到达前面的高度的 因为这样才能保证每个 乌龟只用了一次 不是背包胜似背包
#include <iostream> #include<cstdio> #include<string.h> #include<algorithm> using namespace std; const int maxn=5610; const int maxv=2147483647; struct turtles{ int weight,stength; bool operator < (const turtles &A)const{ return stength<A.stength; } }T[maxn]; int minweigh[maxn]; int minv(int a,int b){ return a>b?b:a; } int main() { int w,s,n=1; while(cin>>w>>s){ if(w>s)continue; T[n].weight=w; T[n].stength=s; n++; } for(int i=1;i<n;i++) minweigh[i]=maxv; minweigh[0]=0; sort(T+1,T+n); int maxh=0; for(int i=1;i<n;i++){ for(int j=n-1;j>=1;j--){ if(minweigh[j-1]!=maxv&&minweigh[j-1]+T[i].weight<=T[i].stength){ minweigh[j]=minv(minweigh[j],T[i].weight+minweigh[j-1]); maxh=maxh>j?maxh:j; } } } printf("%d\n",maxh); return 0; }
uva 10201 这题说的是给了 一个从起点到终点的 距离然后 还有在这之间的加油站和油价 然后从起点开始的 油箱是半满状态的 到达终点也必须是半满状态或者更多 然后计算最小花费
这里 可以比较简单的列出动态方程 考虑每个加油站是否进去加 然后加得的状态的价钱是多少即可以从别的状态转移而来 又可以从自己的加油站转化而来 可得dp[i][j]=min(dp[i-1][j+dist[i][j]],dp[i][j],dp[i][j-1]+T[i].per] 然后就得到了解
#include <iostream> #include<cstdio> #include<string.h> #include<algorithm> using namespace std; const int maxn=105; const int maxv=2147483647; struct station{ int dist,per; bool operator <(const station &A)const { return dist<A.dist||(dist==A.dist&&per<A.per); } }T[maxn]; int dp[maxn][maxn*2]; int minv(int a,int b){ return a>b?b:a; } int main() { int cas; char str[100]; scanf("%d",&cas); while(cas--){ int dist; scanf("%d",&dist); getchar(); int n=1; while(gets(str)){ if(strlen(str)==0) break; sscanf(str,"%d%d",&T[n].dist,&T[n].per); ++n; } sort(T+1,T+n); T[0].dist=0; T[0].per=2147483647; for(int i=0;i<n;i++) for(int j=0;j<=200;j++) dp[i][j]=maxv; dp[0][100]=0; for(int k=1;k<n;k++){ int G=T[k].dist-T[k-1].dist; for(int i=0;i<=200;i++){ if(i+G<=200&&dp[k-1][G+i]!=maxv) dp[k][i]=dp[k][i]>dp[k-1][i+G]?dp[k-1][i+G]:dp[k][i]; if(i!=0&&dp[k][i-1]!=maxv) dp[k][i]=dp[k][i]>dp[k][i-1]+T[k].per?dp[k][i-1]+T[k].per:dp[k][i]; } // for(int i=0;i<=200;i++){ printf("%d ",dp[k][i]); } // printf("\n"); } int ma=maxv; for(int i=0;i<n;i++){ int d=dist-T[i].dist>0?dist-T[i].dist:T[i].dist-dist; for(int j=100+d;j<=200;j++) ma=minv(dp[i][j],ma); } if(ma==maxv) printf("Impossible\n"); else printf("%d\n",ma); if(cas!=0)printf("\n"); } return 0; }
uva10453 这题说的是给了一个串然后将他变成回文串 花费最小 然后这题好像比较简单 直接在求回文串的 最小添加个数的时候直接加上一下标记 然后再把标记读出来便可
dp[i][j]=min(dp[i+1][j-1],dp[i][j-1]+1,dp[i+1][j]+1);
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int maxn=1002; const int maxv=2000; int dp[maxn][maxn]; int top[maxn][maxn]; char str[maxn],aim[2*maxn]; int main() { memset(dp,0,sizeof(dp)); while(scanf("%s",str)==1){ int len=strlen(str); for(int i=0;i<=len;i++) for(int j=i;j<=len;j++) {dp[i][j]=i==j?0:maxv; top[i][j]=3; } for(int k=1;k<len;++k){ for(int i=0;k+i<len;++i){ int j=k+i; if(str[i]==str[j]){ if(dp[i][j]>dp[i+1][j-1]) { dp[i][j]=dp[i+1][j-1]; top[i][j]=3;} } if(dp[i][j]>dp[i+1][j]){ dp[i][j]=dp[i+1][j]+1; top[i][j]=1; } if(dp[i][j]>dp[i][j-1]){ dp[i][j]=dp[i][j-1]+1; top[i][j]=2; } } } int L=0,R=dp[0][len-1]+len-1,k1=0,k2=len-1; aim[R+1]=0; while(L<=R&&k1<=k2){ if(top[k1][k2]==3){ aim[L]=str[k1];aim[R]=str[k2]; k1++;k2--; } else if(top[k1][k2]==2){ aim[L]=str[k2];aim[R]=str[k2]; k2--; } else if(top[k1][k2]==1){ aim[L]=str[k1];aim[R]=str[k1]; k1++; } L++;R--; } printf("%d %s\n",dp[0][len-1],aim); } return 0; }
uva 10029 这题题意很清楚 就是找一个能够使得这个串 通过修改一个字符 后得到另外的一个串 他给的顺序是字典序递增的给的
这里有种解法 都是来 大神们的 一种是hash 一种是map 先讲讲map 的做法 （因为hash函数的原理我现在还不明白）
map 是将字符串长度相同的字符串归结到一个集合当中 然后对与当前的这个字符串进行 3种操作 然后得到的 另一个字符串 找修改后的字符串在是否在相应的长度的 map里是否存在相应的 也相当与记忆化搜索
#include <iostream> #include<cstdio> #include<string> #include<map> using namespace std; const int maxn=25005; map<string,int>dict[30]; int steps[maxn]; int exist(int index,string &temp,int step){ map<string,int>::iterator it; it=dict[index].find(temp); if(it!=dict[index].end()) if((steps[(*it).second]+1)>step) step=steps[(*it).second]+1; return step; } int main() { string line,temp; int current=0; int maxmum=0; for(int c=0;c<maxn;c++) steps[c]=1; while(cin>>line){ int index=line.length()-1; int step=1; if(index>0){ for(int i=0;i<=index;i++){ temp=line; if(i==index||temp[i]>=temp[i+1]){ temp.erase(temp.begin()+i); step=exist(index-1,temp,step); } temp=line; while(temp[i]>‘a‘){ temp[i]--; step=exist(index,temp,step); } temp=line; temp.insert(temp.begin()+i,line[i]); if(temp<line) step=exist(index+1,temp,step); while(temp[i]>‘a‘){ temp[i]--; step=exist(index+1,temp,step); } } } else{ temp=line; while(temp[0]>‘a‘){ temp[0]--; step=exist(index,temp,step); } } if(step>maxmum){ maxmum=step; } steps[current]=step; dict[index].insert(make_pair<string,int>(line,current)); current++; } cout<<maxmum<<endl; return 0; }
突然发现自己对于hash 一点感觉都没有 这题hash 就是 对于每个字符串进行一次hash 然后 使得在线性的时间内能够 找到他们 因为他给的顺序是字典序 然后对于每个字符串找出他所能变成的字符串 如果存在就 dp[n]=max(dp[k]+1,dp[n]) 因为如果数据不要太坑还是可以接受的 这样就得的到了 相应的 最长递增子序列 LIS 然后时间算下 在查找时间接近于线性的情况下 25000*26*16*3还是能接受的
终于使用hash 做了第一题 看题解的
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int hash=1000003; const int maxn=25005; int head[hash]; int next[maxn],dp[maxn]; char temp[20],rt[maxn][20]; int HASH(char *str){ int v=0,seed=131; int len=strlen(str); for(int i=0;i<len;i++) v=v*seed+str[i]; v=(v&0x7fffffff)%hash; return v; } void insert(int s){ int h=HASH(rt[s]); next[s]=head[h]; head[h]=s; } int search(){ int i,h; h=HASH(temp); for( i=head[h];i!=-1;i=next[i]) if(strcmp(rt[i],temp)==0) break; return i; } int exit(int step){ int h=search(); if(h!=-1){ if(dp[h]+1>step) step=dp[h]+1; } return step; } void del(int f,int d,int n){ int i=0,j=0; while(i<d&&j<n){ temp[i]=rt[f][j]; i++;j++; } j++; while(j<n){ temp[i]=rt[f][j];i++;j++; } temp[i]=0; } void add(int f,int d,int n){ int i=0,j=0; while(j<n&&i<d){ temp[i]=rt[f][j]; i++;j++; } temp[i++]=rt[f][j]; while(j<n){ temp[i++]=rt[f][j++]; } temp[i]=0; } int main() { memset(head,-1,sizeof(head)); int n=0,step=0,maxlen=0; while(scanf("%s",rt[n])==1){ int len=strlen(rt[n]); step=1; for(int i=0;i<len;i++){ if(len>1&&(i+1==len||rt[n][i]>=rt[n][i+1])){ del(n,i,len); if(strcmp(temp,rt[n])<0){ step=exit(step); } } strcpy(temp,rt[n]); while(temp[i]>‘a‘){ temp[i]--; step=exit(step); } add(n,i,len); while(temp[i]>‘a‘){ temp[i]--; step=exit(step); } } insert(n); maxlen=maxlen>step?maxlen:step; dp[n]=step; n++; } printf("%d\n",step); return 0; }
uva 10313 这题说的是 有一个面值不超过 300 的n 元 然后让你用多少种方法将他 拼起来 注意这里是说的是 比如 6 由3 张货币组成那么就有 3种方法 即 1 1 4 、1 2 3、2 2 2 ，然后计算法 对于一个 给定的数 被几个 面值组成的 方法总数
这题刚开始并没有 发现可以有什么好的方法可以解决 然后 将他们每个数减去1 比如 1 1 4 减去1 后得到 的是0 0 3 、0 1 2 、1 1 1刚好跟3 有关 分别是 3 的1 2 3 分布
你、由此就可以推得我们所想要的 dp[i][k]+=dp[i-k][L] 记得 dp[0][1]=1; 这是边界 然后还是狂wa 不停 原来 dp[0][0]也要等于1 但是不解的事 dp[0][1] 等于 1 难道有 面值为0的货币 ？？
#include <iostream> #include <cstdio> #include<string.h> using namespace std; long long dp[350][350]; int main() { memset(dp,0,sizeof(dp)); dp[0][0]=dp[0][1]=1; for(int k=1;k<=300;k++) for(int i=k;i<=300;i++){ for(int L=1;L<=k;L++) dp[i][k]+=dp[i-k][L]; } char str[100]; while(gets(str)){ int a1,a2,n; int g=sscanf(str,"%d%d%d",&n,&a1,&a2); if(a1>300)a1=300; if(a2>300) a2=300; if(g==1){ a1=0;a2=n; } if(g==2){ a2=a1; a1=0; } long long sum=0; for(int i=a1;i<=a2;++i) sum=sum+dp[n][i]; printf("%lld\n",sum); } return 0; }
uva 10401这题说的是 给了一个国际象棋的棋盘 本来是一个皇后可以向 8个方向攻击然后 现在 只能够在列上 没有阻碍 在其他 6个方向上就只能够在相邻的一格攻击
现在要考虑的问题是 到底这个地方能不能够放一个皇后 对 了 题 目 必须 要 放 n 个 皇 后 在 n * n 的 方 格 内 那么 我们在想 到底这个地方能不能放皇后 首先 在他攻击的范围内是不能有皇后的 好像只有这一个限制 接下来的 工作就剩下 这个方案数了 如果这个地方放了 那么他可以有几种方法 好在题目中他只能够攻击他的右边 右上 右下 一格的地方 这样就转化成了 第一列和第二 就是列与列之间的关系 呵呵 现在动态方程就 可以得到了 dp[row][colnum]+=dp[i][colnum-1]; 自然边界是在第一列 如果第一列有皇后 那么只要在 放皇后的地方 dp[i][j]=1其他的就不用了 因为这样 只有一种方法 在第一列 ok 好的 那么在第一列中要是没有那该怎么办 当然是 dp[i][1](i=1...len) 因为每个位置都可能是一种情况 哈哈 这样就的解了 好像每次都 首先 wa的稀里糊涂的 然后 在稀里糊涂的A了 可能是 能力还不足
#include <iostream> #include <cstdio> #include <string.h> using namespace std; const int maxn=20; bool map[maxn][maxn]; bool column[maxn]; long long dp[maxn][maxn]; int xx[]={0,0,1,-1,1,-1,-1,1}; int yy[]={1,-1,0,0,1,-1,1,-1}; int absint(int a){ return a>0?a:-a; } bool jud(int row,int co){ for(int i=0;i<8;i++){ int x=row+xx[i]; int y=co+yy[i]; if(map[x][y]) return true; } return false; } int main() { char str[20]; while(scanf("%s",str)==1){ memset(dp,0,sizeof(dp)); memset(map,false,sizeof(map)); memset(column,false,sizeof(column)); int len=strlen(str); for(int i=0;i<len;i++) if(str[i]!=‘?‘) { int G; if(str[i]>=‘0‘&&str[i]<=‘9‘) G=str[i]-‘0‘; if(str[i]>=‘A‘&&str[i]<=‘F‘) G=str[i]-‘A‘+10; column[i+1]=true; map[len-G+1][i+1]=true; } for(int i=1;i<=len;++i){ if(map[i][1]) dp[i][1]=1; if(column[1]) continue; dp[i][1]=1; } for(int co=2;co<=len;++co){ for(int row=1;row<=len;++row){ if(map[row][co]){ for(int i=1;i<=len;++i) if(absint(row-i)>1) dp[row][co]+=dp[i][co-1]; continue; } if(column[co]==true||jud(row,co)) continue; for(int i=1;i<=len;++i) if(absint(row-i)>1) dp[row][co]+=dp[i][co-1]; } } long long sum=0; for(int i=1;i<=len;i++) sum+=dp[i][len]; printf("%lld\n",sum); } return 0; }
POJ 这题说的是给了 n个人 然后首先第m个人退出 然后在接下来的每k个人退出 约瑟夫环的变形
这样解 如果删除第 k个人 那么原本的 编号我们将他们从0编到n-1;
0 1 2 3 4 5 6 7 8 9 。。。n-1
删除第k个得到
0 1 2 3 k-2 k, k+1...n-1然后 从编号为k的开始编号得到
k k+1 k+2 K+3 . . . n-1.。。。k-1
0 1 2 3 n-1-k n-1
这样不断的 删除下去 然后在通过逆推就可以很容易的得到最后的答案 记得最后再加上一个1 因为刚开始编号是从 0到 n-1 的
#include <iostream> #include<cstdio> using namespace std; int main() { int n,m,k; while(scanf("%d%d%d",&n,&k,&m)==3){ if(n==0&&k==0&&m==0) break; int sum=0; for(int i=2;i<n;i++) sum=(sum+k)%i; sum=(sum+m)%n+1; printf("%d\n",sum); } return 0; }
uva10891 这题说的是 给了 n个数 然后两个人轮流去取数 两个人都很聪明 最后计算 第一个取到得和减去后者取到的差 自然每个人都希望自己的 得到尽量多的数的和
取数的方法是从左到又 或者从右到左 且能连续的取 两个人取来去取的 知道最后的都取完为止
这题在 大白数上有介绍 如果在得到数字之后我们就知道了 我所能取得的最大值那么 敌人所能取得 最大值就是 总和减去 最大值 得到的就是他的最小值
这样 对于每个区间都算他的最大最值 而他的 最大值是在别人取到最小值得基础上得到的 因为总和是不变的嘛
然后就得到 dp[i][j]=sum[i][j]-min(dp[i+1][j]...dp[j][j],dp[i][i]...dp[i][j],0)
你取到最大是建立在别人取到最小的基础上的 这样对于每个先手得到的最大值就算出来了
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int maxn=150; int F[maxn][maxn],G[maxn][maxn],dp[maxn][maxn],S[maxn]; int minv(int a,int b){ return a>b?b:a; } int main() { int n; while(true){ scanf("%d",&n); if(n==0) break; S[0]=0; for(int i=1;i<=n;i++){ int a; scanf("%d",&a); S[i]=S[i-1]+a; G[i][i]=dp[i][i]=F[i][i]=a; } for(int L=1;L<=n;L++){ for(int i=1;i+L<=n;i++){ int j=i+L; int m=minv(F[i][j-1],minv(G[i+1][j],0)); dp[i][j]=S[j]-S[i-1]-m; F[i][j]=minv(dp[i][j],F[i][j-1]); G[i][j]=minv(dp[i][j],G[i+1][j]); } } printf("%d\n",dp[1][n]*2-S[n]); } return 0; }
uva 10859
树形dp
这题 也是 大白书上面的 说的是给了 n个点m条边的树 在每个节点上可以放上一盏灯 该灯可以照亮 与这个点相连的边 然后 计算将所有的边都照亮 的 在使用最小的灯的前提下使得 一条边被两盏灯照亮 最多 lrj 的X=M*A+C 很好 A是要使用的最少的灯的数量 C是 被一盏灯照亮的 边的数量 因为他要使得 被两盏灯照亮的边 尽量的多然后就是说被一盏灯着凉的边尽量的少 这样 这里的M 应该取一个比较大的数 这样是为了保证 X/M =A 自然也不要让他 溢出 这样 在A固定的前提下使得 如果X 越小C也就越小
现在会想为什么他不是选 X=M*A+B 最大呢 因为我们知道 在算A的时候我们同样是使得A的数目尽量的小 而B是要尽量的大 这样显然不可行
在理解了 LRJ的 程序后 感觉他的程序过去复杂 按照自己的 思路又把 他给写了 哈哈时间比他的小 自己努力还是有收获的 下面第一个 LRJ的 第二个我的
感觉 X=M*A+C 这个公式挺厉害的 在一个确定的前提下 X越小越好
#include <iostream> #include<cstdio> #include<string.h> #include<vector> using namespace std; const int maxn=1005; int dp[maxn][2],vis[maxn][2]; vector<int>adg[maxn]; int minv(int a,int b){ return a>b?b:a; } int dfs(int i,int j,int f){ if(vis[i][j]) return dp[i][j]; vis[i][j]=1; int &ans=dp[i][j]; ans=2000; for(int k=0;k<adg[i].size();++k) if(adg[i][k]!=f) ans+=dfs(adg[i][k],1,i); if(!j&&f>=0)++ans; if(j||f<0){ int sum=0; for(int k=0;k<adg[i].size();++k) if(adg[i][k]!=f) sum+=dfs(adg[i][k],0,i); if(f>=0)++sum; ans=minv(sum,ans); } return ans; } int main() { int n,m,T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); for(int i=0;i<n;++i) adg[i].clear(); for(int i=0;i<m;++i){ int a,b; scanf("%d%d",&a,&b); adg[a].push_back(b); adg[b].push_back(a); } int ans=0; for(int i=0;i<n;i++) if(vis[i][0]==0) ans+=dfs(i,0,-1); printf("%d %d %d\n",ans/2000,m-(ans%2000),ans%2000); } return 0; }
#include <iostream> #include<cstdio> #include<string.h> #include<vector> using namespace std; const int maxn=1005; int dp[maxn][2],vis[maxn]; vector<int>adg[maxn]; int minv(int a,int b){ return a>b?b:a; } void dfs(int g,int f){ if(vis[g]) return ; vis[g]=1; int sum=0,ans=2000; for(int i=0;i<adg[g].size();++i) if(adg[g][i]!=f){ int to=adg[g][i]; dfs(to,g); ans+=minv(dp[to][0]+1,dp[to][1]);//dp[to][0]+1 是 他的儿子不 放灯 这样就有一条 只被一盏灯照亮的 边了 sum+=dp[to][1]+1;//这里加 1 是因为 他自身不放灯他的儿子放灯 那么自然也形成了 一条 只放一盏灯的边 } dp[g][1]=ans; dp[g][0]=sum; return ; } int main() { int n,m,T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); for(int i=0;i<n;++i) adg[i].clear(); for(int i=0;i<m;++i){ int a,b; scanf("%d%d",&a,&b); adg[a].push_back(b); adg[b].push_back(a); } int ans=0; for(int i=0;i<n;i++) if(vis[i]==0&&adg[i].size()>0){ dfs(i,-1); ans+=minv(dp[i][0],dp[i][1]); } printf("%d %d %d\n",ans/2000,m-(ans%2000),ans%2000); } return 0; }
uva11151 这题说的是 给了一个 字符串然后从这个字符串中删除 字符 使得剩下来的 字符串是回文串 记得用get 他说了 空字符串也是回文串
然后 当 str[i]==str[j] 时dp[i][j]=min(dp[i+1][j-1],dp[i+1][j],dp[i][j-1]) 不等的时候 dp[i][j]=minv(dp[i+1][j],dp[i][j-1]);
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int maxn=1005; int dp[maxn][maxn]; int minv(int a,int b){ return a>b?b:a; } int main() { int t; char str[maxn]; scanf("%d",&t); getchar(); while(t--){ gets(str); int len=strlen(str); for(int i=0;i<=len;i++) for(int j=i;j<=len;j++) dp[i][j]=0; for(int k=1;k<=len;++k) for(int i=0;i+k<len;++i){ int j=i+k; if(str[i]==str[j]) dp[i][j]=minv(dp[i+1][j-1],minv(dp[i+1][j]+1,dp[i][j-1]+1)); else dp[i][j]=minv(dp[i+1][j]+1,dp[i][j-1]+1); } printf("%d\n",len-dp[0][len-1]); } return 0; }
UVA 10911 这题是 集合上的dp 给了2*n个点 计算这些点 两个两个点 搭配 一个点只能搭配一个点 距离的最小和 这样说
既然每个点都要配对，很容易把问题看成如下的多阶段决策过程 先确定P0 和谁配对，然后是P1 接下来是P2。。。Pn 但是对于这个点之前已经定好和谁配对 的 后来又来了一个点 这个点和原来的某个点 配对会取得最大值 这样 就不行了 集合！！！ 集合可以表示任意个 点之间的组合 数据不大 16 个点 二进制集合 并不是非常的大 然后在一个集合当中 如果 刚添进来一个点i 那么这个点 和 集合 中的 j点搭配 那么搭配后的结果就是 dp[S]=min(dp[S],dp[S^(1<<i)^(q<<j)]) 这样就从小的集合 找到了大的集合
#include <iostream> #include<cstdio> #include<string.h> #include<cmath> using namespace std; const double INF=1.79769e+308; const int maxn=20; double dist[maxn][maxn],x[maxn],y[maxn]; double dp[1<<20]; double minv(double a,double b){ return a>b?b:a; } double cat(int a,int b){ double xx=x[a]-x[b],yy=y[a]-y[b]; xx=sqrt(xx*xx+yy*yy); return xx; } int main() { int n,num=1;; char str[30]; while(true){ scanf("%d",&n); if(n==0) break; n=2*n; for(int i=0;i<n;i++){ scanf("%s%lf%lf",str,&x[i],&y[i]); for(int j=0;j<=i;++j) dist[i][j]=dist[j][i]=cat(i,j); } dp[0]=0; for(int S=1;S<(1<<n);++S){ dp[S]=INF; int i,j; for( i=0;i<n;++i) if(S&(1<<i)) break; for(j=i+1;j<n;++j) if(S&(1<<j)){ dp[S]=minv(dp[S],dist[i][j]+dp[S^(1<<i)^(1<<j)]); } } printf("Case %d: %.2lf\n",num,dp[(1<<n)-1]); num++; } return 0; }
uva 10635 lCS 最长公共子序列 这题说的都是 王子和公主在玩游戏 从1 这个点走到 n*n 这个点 每个人只能走某个点一次 国王叫他们同意路线 使得他们的路线上 相对位置所走的 公共点尽量的多 这题很容易想到时最长公共子序列问题 难的是 他这里有 n*n个点 n<=250 太大了 显然是行不通的 这样将最长公共子序列进行转化 因为我们要知道的只是王子和公主的最长公共子序列 找的是相对位置 按照 公主走得顺序给每个点编号 1,2,3,4,5 然后在王子所走的 点中 如果在 公主 所走的路线中出想过就把 这个点的标号 加入王子可能与公主走一样的点的序列中 相对位置不能发生改变 如果没出现过呢 当然可以直接省略掉 因为他已经不可能是公共的点了 接下来来个最长递增之序列 为什么呢 因为我们给公主所走的 点已经进行了标号 是按照 走的点的顺序 的 而且 一个点只出现一次 王子所走的路是按照公主给的点的顺序编号的 这样要 使得 他们的 路程中公共点 最多的话就变得 只要求最长递增子序列了 这样就保证了他们的 相对位置经过的 点最长
#include <iostream> #include<string.h> #include<cstdio> using namespace std; const int maxn=255; int price[maxn*maxn],pricess[maxn*maxn]; int dp[maxn*maxn]; int Birthser(int gh,int n){ int L=0,R=n,mid; while(L<R){ mid=(L+R)/2; if(dp[mid]>=gh) R=mid; else L=mid+1; } return R; } int main() { int t,n,q,p; scanf("%d",&t); for(int cas=1;cas<=t;++cas){ scanf("%d%d%d",&n,&p,&q); memset(price,0,sizeof(price)); for(int i=1;i<=p+1;++i){ int a; scanf("%d",&a); price[a]=i; } int Len=0,maxlen=1; for(int i=0;i<q+1;++i){ int a; scanf("%d",&a); if(price[a]!=0)pricess[Len++]=price[a]; } n=Len; dp[0]=pricess[0]; Len=1; for(int i=1;i<n;++i){ if(dp[Len-1]<pricess[i]){ dp[Len++]=pricess[i]; }else { int Loca=Birthser(pricess[i],Len); dp[Loca]=pricess[i]; } maxlen=maxlen>=Len?maxlen:Len; } printf("Case %d: %d\n",cas,maxlen); } return 0; }
uva 10564 这题说的给了一个类似杨辉三角的东西不过是 沙漏状的 然后 计算从最上面一行 走到最后一行的 总和为S的 方案数 并输出起点最小 的 字典序最小的 方案数 是这样想的 对于每个点 所能到达的值取决于他的两个儿子 只不过是在他的两个儿子所能达到的最状态的前提下加上了他本身的值 dp[i][j][k]=dp[i+1][左][k-T]+dp[i+1][右][k-T]
记得用 long long wa了几发 在这里 没考虑好数据的范围
#include <iostream> #include<string.h> #include<cstdio> using namespace std; const int maxn=25; long long dp[maxn*2][maxn][550]; int F[maxn*2][maxn]; int add(int a){ return a<0?-a:a; } int main() { int n,S; while(true){ scanf("%d%d",&n,&S); if(n==0&&S==0) break; memset(dp,0,sizeof(dp)); for(int i=0;i<2*n-1;++i) for(int j=0;j<add(n-1-i)+1;++j) scanf("%d",&F[i][j]); int L=2*n-2; int G=n-1; for(int i=0;i<n;++i){ dp[L][i][F[L][i]]=1; } int num=n+1; for(int i=L;i>=G;--i){ num--; for(int j=0;j<num;++j) for(int k=0;k<=500;++k) dp[i][j][k+F[i][j]]+=dp[i+1][j][k]+dp[i+1][j+1][k]; } num=1; for(int i=G-1;i>=0;--i){ num++; for(int j=0;j<num;++j) for(int k=0;k<=500;++k){ if(j-1>=0) dp[i][j][k+F[i][j]]+=dp[i+1][j-1][k]; if(j<num-1) dp[i][j][k+F[i][j]]+=dp[i+1][j][k];} } long long sum=0,ma=30; for(int i=0;i<n;++i) if(dp[0][i][S]!=0){ ma=ma>i?i:ma; sum+=dp[0][i][S]; } printf("%lld\n",sum); if(ma!=30){ printf("%d ",ma); int row=0; while(row<n-1){ if(ma-1>=0&&dp[row+1][ma-1][S-F[row][ma]]!=0){ S-=F[row][ma]; ma=ma-1; printf("L"); } else { S-=F[row][ma]; printf("R"); } row++; } while(row<2*n-2){ if(dp[row+1][ma][S-F[row][ma]]!=0) { S-=F[row][ma]; printf("L"); } else{ S-=F[row][ma]; printf("R"); ma=ma+1; } row++; } } printf("\n"); } return 0; }
uva622 这题说的是 给了 n个 快餐店的具体位置然后 然后在这n个快餐店中 选k个 当原料供应站 使得 运输到材料到 每一点的 的运输费用 最少并且输出管辖范围
首先呢 就按照他 给的方法去想 当每增加一个的时候 肯定是在上一个的基础上的 因为 在 【i j】 范围内用两个原料供应点 那么肯定是这两个 点分摊这个区间 那么就枚举这些点 [i][r]管辖一个 [r+1][j]被另一个管辖 然后得到状态 dp[i][j][k]=min(dp[i][r][1]+dp[r+1][j][k-1]) 因为每次都是 添加一个 状态取决与前面已经添加的 为什么不是 dp[i][r][k-1]+dp[r+1][j][1]
你可以想想 我们已将将他们 处理好了 无论你用 前者还是后者得到的结果是一样的 只不过是出现的 顺序不一样，
#include <iostream> #include<cstdio> #include<string.h> #include<algorithm> using namespace std; const int maxn=205; const int maxv=0x7fffffff; struct node{ int x,d; }vis[maxn][maxn][35]; struct adg{ int L,R; bool operator <(const adg &T)const { return L<T.L; } }FT[35]; int dp[maxn][maxn][35]; int local[maxn][maxn]; int sum[maxn],n,m,num; void solve(){ for(int k=2;k<=m;++k){ for(int L=k-1;L<=n;++L){ for(int i=1;i+L<=n;++i){ int j=i+L; dp[i][j][k]=maxv; for(int r=i;r<j;++r){ if(dp[i][j][k]>dp[i][r][1]+dp[r+1][j][k-1]){ dp[i][j][k]=dp[i][r][1]+dp[r+1][j][k-1]; vis[i][j][k].d=r+1; } } } } } } void dfs(int L,int R,int k){ if(k==1){ FT[num].L=L; FT[num].R=R; num++; return ; } FT[num].L=L; FT[num].R=vis[L][R][k].d-1; ++num; dfs(vis[L][R][k].d,R,k-1); } int look(int L,int R,int h){ int s=0; for(int i=L;i<=R;++i) { int L=sum[i]-sum[h]; L=L>0?L:-L; s+=L; } return s; } int main() { int cas=1; while(true){ scanf("%d%d",&n,&m); if(n==0&&m==0) break; num=0; memset(local,0,sizeof(local)); memset(dp,0,sizeof(dp)); sum[0]=0; for(int i=1;i<=n;++i){ scanf("%d",&sum[i]); } for(int L=0;L<=n;++L){ for(int i=1;i+L<=n;++i){ int ma=maxv,lol; for(int j=i;j<=i+L;++j){ int T=look(i,L+i,j); if(ma>T){ ma=T; lol=j; } } local[i][i+L]=lol; dp[i][i+L][1]=ma; } } solve(); dfs(1,n,m); sort(FT,FT+num); printf("Chain %d\n",cas++); for(int i=1;i<=m;++i){ printf("Depot %d at restaurant %d serves ",i,local[FT[i-1].L][FT[i-1].R]); if(FT[i-1].L==FT[i-1].R){ printf("restaurant %d\n",FT[i-1].L); } else { printf("restaurants %d to %d\n",FT[i-1].L,FT[i-1].R); } } printf("Total distance sum = %d\n",dp[1][n][m]); printf("\n"); } return 0; }
uva 10626 这题说的是 每瓶可乐 8 圆 给了 1 5 6 种硬币 个个数 a b c 然后这样就可以得到 一次性只能 买一瓶 然后你给了 贩卖机 多少钱 钱减去 8 剩下的 按最少的张数给你
开了一个 3 维的 数组 分别存他们的状态 得到 dp[a][b][c] 分别是 键 8张 一块的 。2 张5 块的 返回 2张 一块的 。 一张10块的 返回两张一块的 。一张10快加 2张1块返回 一张5块 然后 还有 一张5块加 3张 1块的 。加上记忆化搜索
#include <iostream> #include<cstdio> #include<string.h> using namespace std; int dp[705][105][51]; int minv(int a,int b){ return a>=b?b:a; } int dfs(int A,int B,int C,int ret){ if(ret==0) return 0; if(dp[A][B][C]!=-1) return dp[A][B][C]; int mix=2147483647; if(C>0){ mix=minv(mix,dfs(A+2,B,C-1,ret-1)+1); } if(C>0&&A>=3){ mix=minv(mix,dfs(A-3,B+1,C-1,ret-1)+4); } if(B>=2){ mix=minv(mix,dfs(A+2,B-2,C,ret-1)+2); } if(B>0&&A>=3){ mix=minv(mix,dfs(A-3,B-1,C,ret-1)+4); } if(A>=8){ mix=minv(mix,dfs(A-8,B,C,ret-1)+8); } return dp[A][B][C]=mix; } int main() { int t; scanf("%d",&t); while(t--){ memset(dp,-1,sizeof(dp)); int N,A,B,C; scanf("%d%d%d%d",&N,&A,&B,&C); dfs(A,B,C,N); printf("%d\n",dp[A][B][C]); } return 0; }
uva 10118 这题说的是 给了四堆得 糖果 然后 每个糖果都有颜色 然后Little Bob 只有 一个篮子 每个篮子只能放 最多5 个糖果 然后如果篮子中有 连个颜色相同的糖果 那么这两个糖果可以拿出来篮子里的糖果就是 原本个数减去 2 然后 问Little BOb 可以拿出多少对这样相同颜色的糖果，
这题刚看到题目时 不知怎么下手 然后就按照暴力的想法 想了一下状态主要是 4个堆 的每个位置 不同造成的 然后 就记录状态 记忆化搜索 取最大值
#include <iostream> #include<string.h> #include<cstdio> using namespace std; int dp[41][41][41][41],n; int M[4][41]; int num[25]; int maxv(int a,int b){ return a>b?a:b; } int dfs(int L0,int L1,int L2,int L3){ int sum=0,G=0; if(dp[L0][L1][L2][L3]!=-1) return dp[L0][L1][L2][L3]; for(int i=0;i<=20;++i){ if(num[i]>1) sum+=num[i]/2; if(num[i]%2!=0) G++; } if(dp[L0][L1][L2][L3]!=-1) return dp[L0][L1][L2][L3]; if(G==5){ return dp[L0][L1][L2][L3]=sum; } int ma=sum; if(L0<n){ num[M[0][L0]]++; ma=maxv(dfs(L0+1,L1,L2,L3),ma); num[M[0][L0]]--; } if(L1<n){ num[M[1][L1]]++; ma=maxv(dfs(L0,L1+1,L2,L3),ma); num[M[1][L1]]--; } if(L2<n){ num[M[2][L2]]++; ma=maxv(dfs(L0,L1,L2+1,L3),ma); num[M[2][L2]]--; } if(L3<n){ num[M[3][L3]]++; ma=maxv(dfs(L0,L1,L2,L3+1),ma); num[M[3][L3]]--; } return dp[L0][L1][L2][L3]=maxv(ma,dp[L0][L1][L2][L3]); } int main() { while(true){ scanf("%d",&n); if(n==0) break; for(int i=0;i<n;++i) for(int j=0;j<4;++j) scanf("%d",&M[j][i]); memset(dp,-1,sizeof(dp)); memset(num,0,sizeof(num)); dfs(0,0,0,0); printf("%d\n",dp[0][0][0][0]); } return 0; }
uva 607 这题说的是 有N个课题每个课题要花ti每种解决 每节课都有L分钟 然后不能在两节课都讲有同样的一个课题 就是说要讲就必须在一节课内讲完
然后要求用最少的课时 讲完这些课题 还有最小的不满意度 不满意度是这样计算的 当下课时间为0 时 不满意度增加0 时间1到10之间时 不满意度增加-C 时间在 10 以上的时候不满意度 为 （t-10）*（t-10） 然后在满足最小的 课时前提下最小的 不满意度
刚开始想也是可能在一节课内有多少个课题 然后觉得 肯定跟 所处的状态有关 然后用 背包去做了一下 爆栈了 然后 采用记忆化搜索 过了
记忆化搜索这样鲁 dp[i][j] 表示第i个课题在第j节课 得到的最小的不满意度 枚举每个区间所能达到的所有情况
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int inf=0x7fffffff; int dp[1005][1005]; bool vis[1005][1005]; int ti[1005],n,L,C; int get(int s){ if(s==0) return 0; if(s>0&&s<=10) return -C; if(s>10) return (s-10)*(s-10); } int minv(int a,int b){ return a>b?b:a; } int dfs(int num, int lca){ if(vis[num][lca]) return dp[num][lca]; int sum=0; if(num==0) return lca>0?inf:0; for(int i = lca;i > 0; i -- ){ sum += ti[i]; if( sum > L ) break; int E = dfs( num-1, i-1); if(E != inf){ dp[num][lca] = minv(dp[num][lca],get(L-sum)+E); } } vis[num][lca] = true; return dp[num][lca]; } int main() { int cas=0; while(true){ scanf("%d",&n); if(n==0) break; scanf("%d%d",&L,&C); for(int i = 1;i <= n;++ i) scanf("%d",&ti[i]); int M=0,num=0; for(int i = 1;i <= n; i ++) if(M<ti[i]){ num++; M=L-ti[i]; } else M=M-ti[i]; for(int i = 0;i <= num;++ i) for(int j = 0 ; j <= n ; ++ j ) dp[i][j]=inf; memset(vis,false,sizeof(vis)); dfs(num,n); if(cas!=0) printf("\n"); printf("Case %d:\n",++cas); printf("Minimum number of lectures: %d\n",num); printf("Total dissatisfaction index: %d\n",dp[num][n]); } return 0; }
经过调试 昨晚太糊涂了 精神不足 自己将fii（）的填充量变大了 然后爆栈了 今天改了一下 背包也过了
#include <iostream> #include<cstdio> #include<string.h> #include<queue> using namespace std; const int inf=0x7fffffff; struct node{ int num,ret,loc; node(int a=0,int b=0,int c=0){ num=a; ret=c; loc=b; } }; int dp[5005]; int ti[5005],n,L,C; int get(int s){ if(s==0) return 0; if(s>0&&s<=10) return -C; if(s>10) return (s-10)*(s-10); } int minv(int a,int b){ return a>b?b:a; } int main() { node temp,re; queue<node>Q; int cas=0; while(true){ scanf("%d",&n); if(n==0) break; scanf("%d%d",&L,&C); for(int i = 1;i <= n;++ i) scanf("%d",&ti[i]); int M=0,num=0; for(int i = 1;i <= n; i ++) if(M<ti[i]){ num++; M=L-ti[i]; } else M=M-ti[i]; ti[n+1]=500; re=node(0,0,0); fill(dp,dp+num+2,inf); dp[0]=0; int mi=inf ,ma = -1,mg=inf; Q.push(re); for(int i = 1;i <= n;++ i ){ while(!Q.empty()){ if(Q.front().num==i) break; temp=Q.front(); Q.pop(); int R=temp.loc/L; int W=get((R+1)*L-temp.loc-ti[i]); dp[R+1]=minv(dp[R+1],temp.ret+W); if(i==n&&R+1==num) mg=minv(mg,dp[R+1]); mi=R+1<mi?R+1:mi; ma=R+1>ma?R+1:ma; re=node(i,temp.loc+ti[i],temp.ret); if((R+1)*L<re.loc+ti[i+1]) continue; Q.push(re); } for(int j = mi;j <= ma;++ j ) if(dp[j]!=inf){ re=node(i,j*L,dp[j]); Q.push(re); } ma=-1; mi=inf; fill(dp,dp+num+2,inf); } if(cas!=0) printf("\n"); printf("Case %d:\n",++cas); printf("Minimum number of lectures: %d\n",num); printf("Total dissatisfaction index: %d\n",mg); while(!Q.empty())Q.pop(); } return 0; }
uva 10604 集合上的动态规划 这题说的是化学试验室有 N中药品 每种药品可以和别的药品进行混合 混 合 后 会 产 生 一 定 的 热 量 然 后 转 化 为 别 的药品 给了 K 种 药 品 计 算 这 K 种 药 品 混 合 后 的 最 少 热 量 这题应该是 集合 看看数据 略小 然后 dp[S][i] 对于集合S变成 i 化合物后 的最小热量 这样就可以办证是从他的任意子集来的 这样就 得到动态方程
dp[S][i]= min(dp[s][i],dp[s0][i]+sp[s0^s][j]+tow[i][j]);
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int inf=0x7fffffff; int dp[1<<10][10]; int tod[10][10]; int tow[10][10],n,k; int cas[12]; int minv( int a,int b) { return a>b?b:a; } int main() { int t; scanf("%d", &t ); while(t--){ for(int i = 0;i <= n ; ++ i) {tod[0][i] = tod[i][0] =i; tow[0][i]= tow[i][0] = 0; } scanf("%d",&n); for(int i = 1;i <= n; ++ i ) for (int j = 1 ;j <= n ; ++ j) scanf("%d%d", &tod[i][j], &tow[i][j] ); scanf("%d",&k); for(int i=0;i<(1<<k); ++i) for(int j=0; j<=n; ++j) dp[i][j]=inf; for(int i = 0;i < k;i ++ ){ scanf("%d", &cas[i]); dp[ 1 << i ][ cas[i] ] = 0 ; } for(int S = 1;S < ( 1<<k ); ++ S ){ for(int S0 = S;S0; S0= ( S0-1 )&S ){ for(int i = 1;i <= n; ++ i){ if(dp[S0][i] == inf ) continue; for(int j=1; j <= n ; ++j ) { if(dp[ S0^S ][ j ]==inf) continue; dp[S][tod[i][j]]=minv(dp[S][tod[i][j]],dp[S0][i]+dp[S^S0][j]+tow[i][j]); } } } } int sum=inf; for(int i=1 ; i <= n; ++ i ) sum=minv(sum,dp[(1<<k)-1][i]); printf("%d\n",sum); char str[5]; scanf("%s",str); } return 0; }
uva 10913 这题说的是给了 一个矩阵然后从左上到右下 使得经历过的 点数之和最大 然 后 经 过 负 数 的 点 只 能 不超过 K个 然后 有dp[i][j][k] 表示 ij这个点在k这个状态的最大的整数和 然后 只能向左走或则向右或则向下 走 每个格子只能走一次这样我们就可以从左边和从 右边 开始 进行选取 然后每个状态都得到最优的 一个点的多个状态可以由多个点组成 因为答案只要求最大的和 然后得到了
map[i][j]>=0 dp[i][j][k]=max(dp[i+1][j][k]+map[i][j],max(dp[i][j][k],dp[i-+1][k]+map[i][j])(-左边 + 右边)
map[i][j]<0 dp[i][j][k]=max(dp[i+1][j][k-1]+map[i][j],max(dp[i][j][k],dp[i-+1][k-1]+map[i][j])(-左边 + 右边)
#include <iostream> #include<cstdio> #include<string.h> #include<queue> using namespace std; const long long inf=0x7fffffffffffffff; long long dp[3][80][80][10]; int N,K; long long map[80][80]; long long maxv(long long a,long long b){ return a>b?a:b; } void inti(){ for(int u=0;u<3; u++) for(int i = 0; i <= N + 1; ++ i) for( int j = 0 ; j <= N + 1; ++ j) for( int kk = 0;kk <= K ; kk ++ ) dp[u][i][j][kk]=-inf; dp[0][0][1][0]=0; } int main() { int cas=1; while(true){ scanf("%d%d",&N,&K); if(N==0&&K==0) break; for(int i = 1; i <= N; ++ i ) for( int j = 1 ; j <= N ; ++ j) scanf("%lld",&map[i][j]); inti(); for(int i=1;i<= N ; ++ i){ for(int j = 1; j <= N ; ++j ){ int R=N-j+1,L=j; if(map[i][j]>=0) { for(int h=0;h<=K; h++) { dp[1][i][L][h]=dp[0][i-1][L][h]!=-inf?maxv(dp[0][i-1][L][h]+map[i][j],dp[1][i][L][h]):dp[1][i][L][h]; dp[1][i][L][h]=dp[1][i][L-1][h]!=-inf?maxv(dp[1][i][L-1][h]+map[i][j],dp[1][i][L][h]):dp[1][i][L][h]; } } else { for(int h=1;h<=K; h++) { dp[1][i][L][h]=dp[0][i-1][L][h-1]!=-inf?maxv(dp[0][i-1][L][h-1]+map[i][j],dp[1][i][L][h]):dp[1][i][L][h]; dp[1][i][L][h]=dp[1][i][L-1][h-1]!=-inf?maxv(dp[1][i][L-1][h-1]+map[i][j],dp[1][i][L][h]):dp[1][i][L][h]; } } if(map[i][R]>=0){ for(int h=0;h<=K; h++) { dp[2][i][R][h]=dp[0][i-1][R][h]!=-inf?maxv(dp[0][i-1][R][h]+map[i][R],dp[2][i][R][h]):dp[2][i][R][h]; dp[2][i][R][h]=dp[2][i][R+1][h]!=-inf?maxv(dp[2][i][R+1][h]+map[i][R],dp[2][i][R][h]):dp[2][i][R][h]; } }else{ for(int h=1;h<=K; h++) { dp[2][i][R][h]=dp[0][i-1][R][h-1]!=-inf?maxv(dp[0][i-1][R][h-1]+map[i][R],dp[2][i][R][h]):dp[2][i][R][h]; dp[2][i][R][h]=dp[2][i][R+1][h-1]!=-inf?maxv(dp[2][i][R+1][h-1]+map[i][R],dp[2][i][R][h]):dp[2][i][R][h]; } } } for(int j=1;j<=N; ++j) for(int h=0;h<=K; ++h) dp[0][i][j][h]=maxv(dp[1][i][j][h],dp[2][i][j][h]); } long long sum=-inf; for(int i=0;i<=K; ++i) if(dp[0][N][N][i] > sum) sum=dp[0][N][N][i]; if( sum == -inf ) printf("Case %d: impossible\n",cas++); else printf( "Case %d: %lld\n",cas++,sum ); } return 0; }
uva 11008 这题说的是给了n 个 点 然后你有一种激光枪 然后可以一枪将 一排的树 都砍掉 然后让你砍掉 m棵树 最 少 开 的 枪 数 然 后 处 理 好 可 以 在 一 条 线 上 的 点
然 后 枚 举 采 用 集 合 上 的 点 采用集合上的动态规划 可以得到所要的 集合将重点给去掉 我原本以为不可能有 重点 然 wa 了 好 几 发 处 理 好 后 就 过 了
#include <iostream> #include<string.h> #include<cstdio> #include<algorithm> using namespace std; const int inf = 100000; int dp[1<<17],num[17],pointnum; bool vis[1<<17]; struct point{ int x,y; bool operator<(const point &A) const { return x<A.x||(x==A.x&&y<=A.y); } }node[20],T[20]; int n,m,ans; int minv(int a,int b) { return a > b ? b : a; } void work( int H){ int ge=0; for(int i=0; i< pointnum ; ++i) if(H&(1<<i)) ge+= num[i]; if( ge>=m ) ans=minv(dp[H],ans); } void inti(){ for(int i=0 ;i < (1 << pointnum) ; ++ i) dp[i]= inf ; dp[0] = 0; for(int i=0 ;i < pointnum ; ++ i){ dp[1<<i] = 1; if(num[i]>=m) ans=minv(ans,dp[1<<i]); for(int j= i+1 ; j < pointnum; ++ j ){ int x1 = T[i].x - T[j].x; int y1 = T[i].y - T[j].y; int sum=(1<<i); sum+= (1<<j); int ge = num[i] + num[j] ; dp[sum]=1; if(ge >= m) ans=minv(ans,dp[sum]); for(int k = 0 ; k < pointnum ; k ++ ){ if(k==i ||k ==j) continue; int x2 = T[k].x - T[j].x; int y2 = T[k].y - T[j].y; if(x2 * y1 != x1 * y2) continue; sum+=(1<<k); dp[sum]=1; ge+=num[k]; if(ge>=m) ans=minv(ans,dp[sum]); } } } } int main() { int t; scanf("%d",&t); for(int cas = 1; cas <= t ; cas ++ ){ scanf("%d%d",&n,&m); for(int i=0 ;i < (1<<n) ; ++ i) dp[i]=inf; for(int i=0;i < n ; i ++) scanf("%d%d",&node[i].x,&node[i].y); sort(node,node+n); memset(num,0,sizeof(num)); num[0]=1; T[0]=node[0]; pointnum=1; for(int i=1;i < n ; i++){ if(node[i].x==node[i-1].x&&node[i].y==node[i-1].y) num[ pointnum-1 ] ++; else { T[ pointnum ++ ] = node[i]; num[ pointnum - 1 ] = 1 ; } } ans=m; inti(); for(int S=1 ; S < (1<<pointnum) ; ++ S ){ for(int S0 = S ; S0 ; S0 =(S0-1)&S ){ dp[S]=minv(dp[S],dp[S^S0]+dp[S0]); } work(S); } printf("Case #%d:\n",cas); printf("%d\n",ans); if(cas!=t) printf("\n"); } return 0; }
uva10723 这 题 说 的 是 给 了 两 串 字 符 串 然 后 将 这 两 串 字 符 串 合 并 成 一 串, 使 得 这 两 个 字 符 串 与 合 并 的 字 符 串 最 长 公 共 子 序 列 为 各 自 串 的 长 度 ，
先 用 最 长 公 共 子 序 列 求 出 两 个 字 符 合并后的最小长度 然后 进行记忆化搜索 dp[ L ][ h1 ][ h2 ] 表 示 合 成 串 在 L 长 度 的 时 候 字 符 串 在s1 中取到了 h1 个 字符串 s2 取到了 h2 个然后 如果相同的 s1[h1]==s2[h2] 表示下一个他们具有相同的 字符 自然 只有一种情况 如果不相同 那么就 枚举这两个字符放在这个位置的 总数
#include <iostream> #include<cstdio> #include<string.h> using namespace std; int commn[61][61],n,m,Len,L1,L2; long long dp[61][61][61]; char s1[60],s2[60],s3[60]; bool vis[61][61][61]; long long dfs(int Loc){ int h1=0,h2=0; for(int i=0;i < Loc ; i ++) { if(s1[h1]==s3[i]&&h1<L1) ++ h1; if(s2[h2]==s3[i]&&h2<L2) ++ h2; } if(vis[Loc][h1][h2]) return dp[Loc][h1][h2]; if(Loc>=Len){ if(h1 == L1 && h2 == L2) return 1; else return 0; } if(s1[h1]==s2[h2]){ s3[Loc]=s1[h1]; dp[Loc][h1][h2] = dfs(Loc+1); } else { if(h1<L1){ s3[Loc] = s1[h1] ; dp[Loc][h1][h2]+=dfs(Loc+1); } if(h2<L2){ s3[Loc] = s2[ h2 ]; dp[Loc][h1][h2]+=dfs(Loc+1); } } vis[Loc][h1][h2]=true; return dp[Loc][h1][h2]; } int main() { int T; scanf("%d\n",&T); for(int cas=1 ; cas <= T ; cas ++){ memset(vis,false,sizeof(vis)); gets(s1); gets(s2); L1 = strlen(s1); L2 = strlen(s2); memset(commn,0,sizeof(commn)); memset(dp,0,sizeof(dp)); for(int i=1;i <= L1 ; i ++) for( int j = 1; j <= L2 ; ++ j) if(s1[i-1] == s2[j-1]) commn[i][j] = commn[i-1][j-1] + 1 ; else commn[i][j] = commn[i-1][j] > commn[i][j-1] ? commn[i-1][j] : commn[i][j-1]; Len=L1 + L2 - commn[L1][L2]; dfs(0); printf("Case #%d: %d %lld\n",cas,Len,dp[0][0][0]); } return 0; }
uva11258 这 题 说 的 是 给 了 一 个 数 字 字 符 串 然 后 你 将 它 分 割 成 不 超 过 int 范 围 内 的 数 字 然 后 怎 样 分 割 会 得 到 最 大 的 数（ 自 然 是 将 分 割 后 的 每 个 数 字 相 加 ） 额 前 面 有 类 似 的 一个状态表示现在 第dp[LOC][i] 表示 第i 个数字 组成第LOC 个数字时 他以后的数的任意组合能达到的最大值
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const long long maxv=0x7fffffff; long long dp[250][250]; int Len; bool vis[250][250]; char str[400]; long long dfs(int Loc,int num){ if(Loc>=Len||num>=Len) return 0; if(vis[Loc][num]) return dp[Loc][num]; long long ans=0; for(int i = num ; i < Len ; i ++){ ans = ans * 10 + str[ i ] - ‘0‘; if(ans>maxv) break; long long G=dfs(Loc+1,i+1); dp[Loc][num]=ans+G>dp[Loc][num]?ans+G: dp[Loc][num]; } vis[Loc][num] = true ; return dp[Loc][num]; } int main() { int t; scanf("%d",&t); while(t--){ memset(vis,false,sizeof(vis)); memset(dp,0,sizeof(dp)); scanf("%s",str); Len=strlen(str); dfs(0,0); printf("%lld\n",dp[0][0]); } return 0; }
uva 10599 这题说的是给了一个 网格的 点然后机器人从 左上角到右下角 然后只能向下走或则向右走 问从左上角到右下角最多能够得到几个垃圾 然后得到的垃圾总数是多少 这样我最初以为是走格子 胡乱的 搞了个记忆化搜索 然后得到答案不正确 仔细一看 从一个有垃圾的地方达到另一个有垃圾的地方只能算一次 这样胡乱搞的就不行了 想想他们具有相对顺序 这样对他们进行一次排序 按照x轴和 y轴排小的放前面可以发现 似乎用 LIS 能解 确实不可能到达的点总是能够相互替换的 这样 来了一次LIS 这里是最多的时候可能会出现100*100个点所以 用nlogn的 然后加上一些标记 可以优化 就是记录他的前驱结点最后的位置 这样就省得去找别的不可能的点 然后 在计算方案数的时候采用记忆化搜索 在者 得用高精度 要不然不够 还有压一亿要25 位左右 因为这里wa了 几发 因为我只开了10位的int要、压一亿
#include <iostream> #include<string.h> #include <cstdio> #include <vector> #include <algorithm> #include <stack> using namespace std; const int MOD = 100000000 ; struct node{ int x,y,Per,Loc; bool operator< (const node &A) const{ return x<A.x||(x==A.x&&y<A.y); } }dp[105*105],re[105*105]; struct Bignumber{ int Len; int R[25]; Bignumber(){ Len=1; memset(R,0,sizeof(R)); } }num[105][105]; Bignumber add( Bignumber A, Bignumber B){ Bignumber C ; C.Len=A.Len>B.Len? A.Len : B.Len ; int t = 0; for(int i = 0 ; i < C.Len ; ++ i){ C.R[i]=(A.R[i]+B.R[i] + t)% MOD; t=( A.R[i] + B.R[i] + t)/ MOD ; } if(t>0){ C.R[C.Len] = t; C.Len ++ ; } return C; } int N,row,column,per[500]; bool vis[105][105]; vector<node>tap[205]; int birdseach(int T,node E){ int L = 0,R = T; while(L < R){ int mid=( L + R ) >> 1; if(dp[mid].x <= E.x && dp[mid].y <= E.y ){ L=mid+1; }else R=mid; } if( ( dp[ L ].x <= E.x && dp[ L ].y <= E.y ) ) L++; return L; } Bignumber dfs(int en, int Loc){ node C = tap[en][Loc] ; if(vis[C.x][C.y]) return num[C.x][C.y] ; Bignumber T; node D; int TG = C.Per; if( TG == -1 ) T.R[0] = 1; else { int now = (C.x-1)*column+C.y; node LA= tap[ en - 1 ][TG]; int late = ( LA.x - 1 )*column + LA.y; per[now]=late ; } for(int i = TG ; i >= 0 ; -- i){ D = tap[en-1][i] ; if(!(D.x <= C.x && D.y <= C.y)) continue; T=add(T,dfs( en -1 , i )); } num[ C.x ][ C.y ] = T ; vis[ C.x ][ C.y ] =true; return num[ C.x ][ C.y ]; } int LIS(int ans){ int Len; sort(re,re+ans); Len = 1 ; tap[0].clear(); re[0].Loc=0; re[0].Per=-1; dp[0]=re[0]; tap[ 0 ].push_back(dp[0]); for(int i = 1 ; i < ans ; ++ i ){ if( re[i].x >= dp[Len-1].x && re[i].y >= dp[Len-1].y ){ tap[Len].clear(); re[i].Loc=0; re[i].Per=dp[Len-1].Loc; dp[Len] = re[i]; tap[Len].push_back(re[i]); Len ++; } else{ int intset=birdseach( Len, re[i] ); if(intset==0){ re[i].Loc=tap[0].size(); re[i].Per = -1; dp[0]=re[i]; } else{ re[i].Loc=tap[intset].size(); re[i].Per = dp[intset-1].Loc; dp[intset] = re[i] ; } tap[intset].push_back(re[i]); } } return Len; } void outprot(int Len ,Bignumber an,int cas){ stack<int>R; int r; r=( tap[Len-1][0].x - 1 )* column +tap[Len - 1][ 0 ].y; R.push( r ); while(per[r] != -1){ r=per[r]; R.push( r ); } printf("CASE#%d: %d",cas,Len); printf(" %d",an.R[ an.Len-1 ]); for (int i = an.Len - 2; i >= 0 ; i -- ) printf("%08d",an.R[i]); while(!R.empty()){ printf(" %d",R.top()); R.pop(); } printf("\n"); } int main() { int cas=0,ans; while(true){ int Len ; scanf("%d%d",&row,&column); if(row == -1 && column == -1) break; ans = 0 ; while(true){ scanf("%d%d",&re[ans].x,&re[ans].y); if(re[ans].x == 0 && re[ans].y == 0) break; ++ans ; } Len = LIS(ans); memset(vis,false, sizeof(vis)); memset(per,-1,sizeof(per)); Bignumber an; for(int i = 0 ; i < tap[Len-1].size() ; i ++) an = add( an,dfs( Len -1 , i ) ); if(ans!=0) outprot( Len , an, ++cas ) ; else printf("CASE#%d: 0 0\n",++cas); } return 0; }
uva 10817 这题说的是 要给一个学校招老师 原本有一些老师可以教学 所给的课程 然后还需要招收一些老师使得每个科目至少有两个老师在教 给了所有在职老师招聘老师的 信息 在职老师是一定要招的然后从剩下的老师中 挑一些老师在满足上面的情况下 使得花费最少
刚开始 想用一个8维数组果断 感觉姿势不对 然 后 才 8 门 课 程 然 后 每 门 课 程 要两个人就好 刚好 1<<16的状态 果断能存下来然后进行 每 个 人 对 于 每 个 人 都 有 可 能 的 状 态 进 行 填 充 要 知 道 1<<i 与 1<<(j+S) 位 代 表 的 是 相 同 的 课 程 有一个存在的时候 另一个不存在 说明这门中有一个人 ，如 果 两 个 都 有 那 么 证 明 这门课程已满然后dp[S] 代表的是此状态的最小 花费 然后 好了 对了还有两点 让我wa的 苦不堪言 是这个 首先for(int i=0 ; i< N; i ++ ) 要放在for(int T = (1<<(2*S))-1 ; T >= 0; -- T ) 外面 这样才能保证一个老师只能被招聘一次 我之前是放在里面的 没考虑清楚 还有一个 if( ( T&(1<<j) ) == 0 ) sum+=(1<<(j)); 我写成了 if( ( T&(1<<j) ) == 0 ) sum+=(1<<(j+S)); 也wa了好几发 果断的 修养不够
#include <iostream> #include <cstdio> #include <string.h> #include <cstdio> using namespace std; const long long INF = 0x7fffffffffffffff; long long dp[1<<20],First,cost[105]; int serving[10]; int S,M,N; bool now[105][8]; char str[500]; void read(){ int Len = strlen(str), h=0; bool inq[10]; memset(inq,false,sizeof(inq)); while( h < Len ){ if(str[h] > ‘0‘ && str[h] <= ‘9‘){ if(inq[str[h]-‘1‘]==false) {++serving[str[h]-‘1‘]; inq[str[h]-‘1‘]=true; } } h++; } } void dfs(int num, int G){ if(num>=S){ dp[G] = First; return ; } dfs(num+1,G); if(serving[num]>0){ dfs( num + 1, G+(1<<(num)) ); } if(serving[num]>1){ dfs(num +1 ,G + (1<<(num+S)) + (1<<(num)) ); } } void read2(int L){ int Len = strlen(str),h=0; while(h<Len){ if(str[h]>‘0‘ && str[h] <= ‘9‘) now[L][str[h]-‘1‘]= true; ++ h; } } long long minv(long long a,long long b){ return a>b?b:a; } int main() { while(true){ First = 0 ; scanf("%d%d%d",&S,&M,&N); if(S==0&&M==0&&N==0) break; for(int i = 0 ; i<(1<<(2*S)) ; ++ i ) dp[i] = INF; memset(serving,0,sizeof(serving)); memset(cost,0, sizeof(cost)); memset(now,false,sizeof(now)); for(int i=0 ; i < M ; i++){ long long T; scanf("%lld",&T); First+=T; gets(str); read(); } dfs(0,0); for(int i = 0 ; i < N ; ++ i ){ scanf("%lld",&cost[i]); gets(str); read2(i); } for(int i=0 ; i< N; i ++ ){ for(int T = (1<<(2*S))-1 ; T >= 0; -- T ){ if(dp[T] == INF) continue; int sum=T; for(int j=0; j< S; ++ j){ if(now[i][j]){ if( ( T&(1<<j) ) == 0 ) sum+=(1<<(j)); else if( (T&(1<<(j+S)))==0) sum+=(1<<(j+S)); } dp[sum]=minv(dp[sum],dp[T]+cost[i]); } } } printf("%lld\n",dp[(1<<(S*2))-1]); } return 0; }
uva 10163 这题说的是某公司有N 个仓库 招聘管理员来看管 每个管理员都有一定的能力值Pi，录用他就是要付Pi 元，一个仓库只能让一个人看管 一个管理员可以看管多个仓库，如果他看管了K个仓库 那么这K个仓库的 安全值就为Pi/K 都是整数意思说存在舍去余数，然后公司将最低的 安全值当作这个公司的安全值 求使得安全值最高的前提下招聘的花费尽量的少，这题wa的好痛苦 ，刚开始将dp[i][j] 和 price[i][j]表示为第i个人可以看管几个仓库 此时取到的最大值和相应的最小价钱 然后状态从dp[i][j]=min(dp[i-1][k],P[i]/(j-k))这个求最大的安全值是可行的 但是求最小的价钱不一定行 刚开始就是这里wa了 这样说如果有dp[i-1][k] 非常的大 然后P[i]/(j-K) 非常的小 安全值取决去小的但是价钱并不一定要用dp[i-1][k] 反而可以用比dp[i-1][k]小的安全值只要大于P[i]/(j-K)可能会取到更小的价钱但是这个动态方程却没用表示出来，这样先求出的、所能达到的最大值然后按照这个最大值的前提下去求最小的安全值 我用深搜 暴了时间可能是那里的条件没有判断好，然后改成非递归的过了 纠结了两天
#include <iostream> #include <cstdio> #include<string.h> using namespace std; const long long INF=0x7fffffff; long long dp[35][150],price[35][150],P[35],Q[35]; int N,M; long long minv(long long a,long long b){ return a>b?b:a; } long long maxv(long long a,long long b){ return a>b?a:b; } int main() { while(true){ scanf("%d%d",&N,&M); if(N==0&&M==0) break; memset(dp[0],0,sizeof(dp[0])); memset(price[0],0,sizeof(price[0])); for(int i = 0 ; i <= M ; i ++) for( int j= 0 ; j <=N ; ++j ){ dp[i][j]=0; price[i][j]=INF; } for(int i = 1; i <=M ; ++i) scanf("%lld",&P[i]); for(int i = 1 ; i <= M ; i++){ for(int j= 1 ;j <= N ; ++ j){ dp[i][j]=maxv(dp[i-1][j],P[i]/j); for(int k = 1 ; k < j ; k++) dp[i][j]=maxv(minv(dp[i-1][k],P[i]/(j-k)),dp[i][j]); } } if(dp[M][N]==0){ printf("0 0\n"); continue; } int num=0; for(int i =1 ; i <= M ; ++ i) if(P[i]>=dp[M][N]) Q[++num]=P[i]; for(int i=1; i<=num; i++) for(int j = 1; j <= N ; j ++){ if(Q[i]/j>=dp[M][N]) price[i][j]=minv(price[i-1][j],Q[i]); else price[i][j]=price[i-1][j]; for( int k =1; k< j ; ++ k){ if(price[i-1][k]==INF||(Q[i]/(j-k))<dp[M][N])continue; price[i][j]=minv(price[i][j],price[i-1][k]+Q[i]); } } printf("%lld %lld\n",dp[M][N],price[num][N]); } return 0; }
uva 709 这 题 说 的 是 编 写 一 个 文 本 编 辑器 然 后 使 得 每 行 的宽度相同 每行开头和结尾都必须是单词 有一种情况 就是一行只能容纳下一个单词的 然后每个单词间都会有空格空格的个数c bad=(c-1)^2 为这个不好的度量然后计算使得这个总不好值最小的方案并输出 还有如果有一行一个单词bad就是500 这样采用记忆化搜索使得教前面的行方尽量多的单词 还有在输出的时候尽量让较少的空格放在前面因为样例是这样的
#include <iostream> #include <cstdio> #include <string.h> using namespace std; const int INF= 0x7fffffff; const int maxn = 1015; int dp[maxn][maxn]; int Len[maxn],N,num,per[maxn][maxn]; char str[maxn][85]; void read(){ char t[1005]; getchar(); while(true){ gets(t); int L= strlen(t); if( L==0 ) break; int i=0; while(i<L){ if(t[i]>=33&&t[i]<=126){ int g=0 ; while(t[i]>=33&&t[i]<=126&& i<L){ str[num][g++] = t[i++]; } Len[num]=g; str[num][g]=0; num++; } i++; } } } int cout1(int sum,int ge){ int gap=N-sum; return (gap/ge-1)*(gap/ge-1)*ge+(2*(gap/ge-1)+1)*(gap%ge); } long long dfs(int Loc,int S){ if(dp[Loc][S]!=INF) return dp[Loc][S]; if(S>=num) return 0; dp[Loc][S]=dfs(Loc+1,S+1)+500; per[Loc][S]=S; // if(Len[S] == N )dp[Loc][S]-=500; int sum=Len[S]; for(int i=S+1; i<num; i ++ ){ sum += Len[i]; if(sum+i-S>N)break; int G= cout1(sum,i-S); int T=dfs(Loc+1,i+1); if(G+T<=dp[Loc][S]){ dp[Loc][S] = G+T; per[Loc][S]=i; } } return dp[Loc][S]; } void out(int L,int R){ if(L ==R){ printf("%s\n",str[L]); return ; } printf("%s",str[L]); int ge=R-L; int sum=0; for(int i = L ; i<= R ; ++ i) sum+=Len[i]; int gap = N-sum ; int t=gap/ge; int h = gap%ge; for(int i = L+1 ; i<=L+ge-h ; ++i ) { for( int j= 1 ; j <= t ; ++j ) printf(" "); printf("%s",str[i]); } for(int i= L+ge-h+1; i<=R ; ++i) { for ( int j =0 ; j <=t ; ++j) printf(" "); printf("%s",str[i]); } printf("\n"); } void printw(){ int sta=0,Loc=0; while(per[Loc][sta]!=-1){ out(sta,per[Loc][sta]); sta=per[Loc][sta]+1; Loc++; } } int main(){ while(true){ num=0; scanf("%d",&N); if(N==0 ) break; read(); for(int i = 0 ; i <=num+10 ; i++) for(int j = 0 ; j <=num+10 ; j++) { dp[i][j]=INF; per[i][j]=-1; } dfs(0,0); // printf("%d\n",dp[0][0]); printw(); printf("\n"); } return 0; }
非递归版的 这个确实比较好 因为在不知道单词有多少个的时候这种方法确实比较有利 f[i] 表示以i开头的最小的bad值然后去枚举每个可能的情况
#include <iostream> #include <cstdio> #include <string.h> using namespace std; const int INF= 0x7fffffff; const int maxn = 10150; int dp[maxn]; int Len[maxn],N,num,number[maxn],wide[maxn]; char str[maxn][85]; void read(){ char t[1005]; getchar(); while(true){ gets(t); int L= strlen(t); if( L==0 ) break; int i=0; while(i<L){ if(t[i]>=33&&t[i]<=126){ int g=0 ; while(t[i]>=33&&t[i]<=126&& i<L){ str[num][g++] = t[i++]; } Len[num]=g; str[num][g]=0; num++; } i++; } } } int cout1(int sum,int ge){ int gap=N-sum; return (gap/ge-1)*(gap/ge-1)*ge+(2*(gap/ge-1)+1)*(gap%ge); } void dfs(){ for(int i= num-1 ;i>=0 ; -- i ){ dp[i]=dp[i+1]+500; int sum = Len[i]; wide[i]=sum; number[i] = 1; for(int k = 1; k+i<num ; k++ ){ sum += Len[i+k]; if(sum+k>N) break; int G = cout1(sum,k); if(G+dp[i+k+1]<=dp[i]){ dp[i]=G+dp[i+k+1]; wide[i] = sum ; number[i] =k+1; } } } } void out(int L,int R){ printf("%s",str[L]); int ge=R-L-1; if(ge==0) { printf("\n"); return ; } int gap=N-wide[L]; int t=gap/ge; int h= gap%ge; for (int i=L+1 ; i <=L+ge-h; ++i){ for(int j=1 ;j<=t ; j++)printf(" "); printf("%s",str[i]); } for(int i=L+ge-h+1; i <R; i++){ for(int j= 0; j<= t; j++)printf(" "); printf("%s",str[i]); } printf("\n"); } void printw(){ int m =0 ; while(m<num){ out(m,m+number[m]); m=m+number[m]; } } int main(){ while(true){ num=0; scanf("%d",&N); if(N==0 ) break; read(); for(int i= 0 ; i <num ; i++) dp[i]=INF; dp[num]=0; dfs(); // printf("%d\n",dp[0]); printw(); printf("\n"); } return 0; }
uva 10280 这题说的是给了一个体积为L升的酒 给了N个酒杯 每种酒杯都有自己的最大容量个最低限度也就是说你要用这个酒杯得保证这个酒杯里的酒在这个范围内然后 每种杯子都有无限多个计算最后会有酒没有被装下 我们可以发现这样的情况假设一种杯子有了k个那么在这个k*min----k*max之间的容量的酒是允许被装下的但是随着k的增大会发现这个区间在不断地扩大因为每个相邻区间的距离是固定的min但是右区间的距离是在不断的增大这样随着k的增大会出现一种情况（k+1）*min< k*min可以得到达到这个状态下的k的值就是k大于等于min*min/（max-min）当达到这个区间后的所有值都是可以装下的 然后这样求最大的状态的数就是 max*100 也就是说所有的大于这个状态的酒量都能够被存下来 然后进行完全背包 当我们进行分析后会发现 这些情况下进行完全背包的 不会超过10的7次方3秒因该够了 这个剪支很强大
#include <iostream> #include<cstdio> #include<string.h> using namespace std; const int MAXN = 255*100; const int MAXM = 4500*101; const int INF = 0x7fffffff; int dp[MAXM],v[MAXN],minv[105],maxv[105]; bool vis[MAXM]; void solve(){ int Limt = INF; int L,N; scanf("%d%d",&L,&N); L = L * 1000; for(int i=0 ; i< N ;++ i){ scanf("%d%d",&minv[i],&maxv[i]); if(minv[i]*minv[i]/(maxv[i]-minv[i])<Limt){ Limt = minv[i]*minv[i]/(maxv[i]-minv[i]); } } if(L>=Limt){ printf("0\n"); return ; } int num = 0; memset(vis,false,sizeof(vis)); for(int i= 0 ; i < N ; ++ i ) for(int j = minv[i] ; j<= maxv[i]; ++ j) if(vis[j]==false){ v[num++] = j; vis[j] = true; } memset(dp,0,sizeof(dp)); for(int i = 0 ; i< num ; i++) for( int j=v[i] ; j <=L; j++ ) if(dp[j-v[i]]+v[i]>dp[j]) dp[j] = dp[j-v[i]] + v[i] ; printf("%d\n",L - dp[L] ); } int main() { int t; scanf("%d",&t); while( t -- ){ solve() ; if(t) printf("\n"); } return 0; }
uva 10558 这题说的是给了方格100*100的地图 然后给了几个方格的点的左下角的坐标，然 后 给 了 竖几条线 线 又给了你可以使用的线的条数计算出使得将这些点尽量分开在不同的方格内 输出你使用的横线的位置 这样 如果记忆化搜索会比较好理解 那就用记忆化搜索来讲 dp[i][j] 表示将第一条线放在j这个位置取得的最大值 进行递归的搜索 还有就是num[i][j]表示ij行之间的 点数 然后 这个处理用点小技巧 然后我将 他转化为非递归的形似 然后给的是咱们正常的坐标的 YX 而不是像平常那样的XY 这里wa了几次
#include <iostream> #include <cstdio> #include <string.h> #include <algorithm> using namespace std; const int maxn =105; int num[maxn][maxn],in[maxn][maxn],dp[maxn][maxn],per[maxn][maxn]; int X[maxn*maxn],Y[maxn*maxn],N,NS[maxn],M,A; bool mark[maxn],vis[maxn][maxn]; void dfs(){ dp[A][100]=0; for( int i = A-1; i>0 ; i--){ for( int j = 100-A+i ; j >=i ; j -- ){ int L=j; int R=100-A+i; for( int k =L ; k<=R; k++){ int tt=num[L][k]+dp[i+1][k+1]; if(dp[i][j]<tt){ per[i][j]=k+1; // printf("%d %d %d\n",i,j,per[i][j]); dp[i][j] = tt; } } } } printf("%d",A); int T=1,Loc=1; printf(" %d",1); while(per[T][Loc]!=-1){ printf(" %d",per[T][Loc]); Loc=per[T][Loc]; T++; } printf("\n"); } int main() { while(true){ scanf("%d",&N); if(N==-1)break; for(int i = 0 ; i < N ; ++ i) scanf("%d%d",&Y[i],&X[i]); scanf("%d",&M); for( int i = 0 ; i < M ; ++ i) scanf("%d", &NS[i]); scanf("%d",&A); memset(num,0,sizeof(num)); memset(in,0,sizeof(in)); memset(dp,-1,sizeof(dp)); memset(per,-1,sizeof(per)); sort(NS,NS+M); for( int i = 0 ; i < N ; i ++){ int L= upper_bound(NS,NS+M,Y[i])-NS; in[X[i]][L-1]=1; } for(int i = 1; i<= 100 ; i++){ memset(mark,false,sizeof(mark)); for(int j = 0 ; j< M ; j++) if(in[i][j]){ mark[j]=true; num[i][i]++; } for( int j =i+1; j<=100 ; ++ j) for(int k = 0 ; k< M ; ++ k ){ mark[k]=in[j][k]==1||mark[k]?true:false; if(mark[k])num[i][j]++; } } dfs(); } return 0; }
uva11081 这题说的是给了 三个字符串然后第三个串是由第一个和第二个串的子序列拼接而来的 输出有多少种拼接方案 我是用记忆话搜索的差点T了 先说说我是怎么做的吧 这样dp[i][j][k] 表 示 串 3 是 由 串 1 到 第 j 个 字 符 串 2 到第k个字符组成的 方案 讨论第i个字符给谁的问题
#include <iostream> #include <cstdio> #include <string.h> using namespace std; const int maxn = 65; int dp[maxn][maxn][maxn],d1[maxn][maxn],d2[maxn][maxn],L1,L2,L3; bool vis[maxn][maxn][maxn]; char s1[maxn],s2[maxn],s3[maxn],t1[maxn],t2[maxn]; int maxv( int a, int b){ return a<b?b:a; } int dfs(int loc , int num1 ,int num2){ if(vis[loc][num1][num2]) return dp[loc][num1][num2]; if(loc>=L3){ vis[loc][num1][num2]=true; return dp[loc][num1][num2]=1; } int m1=0,m2=0; for(int i = num1 ;i< L1; i++) if(s1[i]==s3[loc]) m1=(m1+dfs(loc+1,i+1,num2))%10007; else { vis[loc][i+1][num2]=true; dp[loc][i+1][num2]=0; } for( int i = num2 ;i < L2 ; i++) if(s2[i]==s3[loc]) m2=(m2 + dfs(loc+1,num1,i+1))%10007; else { vis[loc][num1][i+1] = true; dp[loc][num1][i+1]=0; } vis[loc][num1][num2]=true; return dp[loc][num1][num2]=(m1+m2)%10007; } int main() { int t ; scanf("%d",&t); while(t --){ memset(dp,0,sizeof(dp)); memset(vis,false,sizeof(vis)); scanf("%s%s%s",s1,s2,s3); L1 = strlen(s1); L2 = strlen(s2); L3 = strlen(s3); dfs(0,0,0); printf("%d\n",dp[0][0][0]); } return 0; }
上面这个差点超时 找了一下题解 发现好强大
f1[i][j][k]= {f1[i][j-1][k] }||(s1[j-1]==s3[i-1]) {f1[i][j-1][k]+f[i-1][j-1][k] };
f2[i][j][k]={f2[i][j][k-1]}||(s2[k-1]==s3[i-1]){f2[i][j][k-1]+f[i-1][j][k-1]};
f[i][j][k] =f1[i][j][k]+f2[i][j][k]
说说我对这几个状态转移的理解 这里感觉说的是 当第一个字符串在s3取到第i个位置的时候s2取到第k个位置的时候f1[i][j][k]=f1[i][j-1][k]表示如果没有他的时候能取到的方案数f1[i][j][k]=f1[i][j-1][k]+f[i-1][j-1][k] 表示的是前面那个状态加上取了这个字符能得到的总状态取了这个点的状态来自 他的前一个状态就是f[i-1][j-1][k]所达到的总状态因为在取他的时候在f[i-1][j-1][k] 状态可能会从f2转移而来，因为他们都是f1[i][j][k]取第j个字符状态的来源
f2[i][j][k]同样的道理 当他们与第一个字符串 初始化的时候就是当第三串是空串的时候可以得到dp[0][i][j]=1;
#include <iostream> #include <cstdio> #include <string.h> using namespace std; const int MOD = 10007; const int maxn=65; int f[maxn][maxn][maxn],f1[maxn][maxn][maxn],f2[maxn][maxn][maxn]; char s1[maxn],s2[maxn],s3[maxn]; int main() { int t; scanf("%d",&t); while(t --){ scanf("%s%s%s",s1+1,s2+1,s3+1); memset(f,0,sizeof(f)); memset(f1,0,sizeof(f1)); memset(f2,0,sizeof(f2)); int L1 = strlen(s1+1); int L2= strlen(s2+1); int L3 = strlen(s3+1); for( int i = 0 ; i <= L1 ; ++ i) for( int j = 0 ; j <= L2 ; ++ j) f[0][i][j]=f1[0][i][j]=f2[0][i][j]=1; for(int k = 1 ; k<= L3 ;k++) for( int i =0 ; i<= L1; ++ i) for(int j = 0 ; j<= L2; ++j){ if(i){ f1[k][i][j]=f1[k][i-1][j]; if(s1[i]==s3[k]) f1[k][i][j]=(f1[k][i][j]+f[k-1][i-1][j])%MOD; } if(j){ f2[k][i][j] = f2[k][i][j-1]; if(s2[j]==s3[k]) f2[k][i][j]= (f2[k][i][j]+f[k-1][i][j-1])%MOD; } f[k][i][j]=(f1[k][i][j]+f2[k][i][j])%MOD; } printf("%d\n",f[L3][L1][L2]); } return 0; }