OJ1001A+B Problem：
a+b。
#include<bits/stdc++.h> using namespace std; int main(){ int a,b; cin>>a>>b; cout<<a+b<<endl; return 0; }
OJ1002阶乘之和
c表示n!因子5的次数，则c=[n/5]+[n/25]+[n/125]+...
末尾0的个数=min(因子2的次数，因子5的次数)=c。
原问题即为n!/(10^c) = x (mod 10)
等价为两个方程：
n!/(10^c) = x (mod 2)
n!/(10^c) = x (mod 5)
分类讨论，
当n<=1时，答案为0 1
当n>1时，第一个方程的解可以是所有偶数，转化为x = 0(mod 2)。
考虑第二个方程，
n!/(10^c)=x (mod 5)
设h(n)=小于等于n且与5互质的数的乘积：
可以分组，因为1*2*3*4 = 6*7*8*9 ...(mod 5)
所以h(n) = (4!)^(n/5)*(n%5)! (mod 5)。
= (-1)^(n/5)*(n%5)! (mod 5)。
n!/(10^c)=h(n)*h(n/5)*...*[(2^c)^-1] = x (mod 5)。
-->(-1)^c*(n%5)!*(n/5%5)!*(n/25%5)!...*(3^c)= x (mod 5)
-->(-1)^c*(3^(c%4))*(n%5)!*(n/5%5)!*(n/125%5)!... = x(mod 5)。
2,5互质，用CRT合并两个方程组
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long int64; int64 n,c; int64 fac(int64 x){int64 res=1;for (int i=1;i<=x;++i) res*=i;return res;} /* c表示n!因子5的次数，则c=[n/5]+[n/25]+[n/125]+... 末尾0的个数=min(因子2的次数，因子5的次数)=c。 原问题即为n!/(10^c) = x (mod 10) 等价为两个方程： n!/(10^c) = x (mod 2) n!/(10^c) = x (mod 5) 分类讨论， 当n<=1时，答案为0 1 当n>1时，第一个方程的解可以是所有偶数，转化为x = 0(mod 2)。 考虑第二个方程， n!/(10^c)=x (mod 5) 设h(n)=小于等于n且与5互质的数的乘积： 可以分组，因为1*2*3*4 = 6*7*8*9 ...(mod 5) 所以h(n) = (4!)^(n/5)*(n%5)! (mod 5)。 = (-1)^(n/5)*(n%5)! (mod 5)。 n!/(10^c)=h(n)*h(n/5)*...*[(2^c)^-1] = x (mod 5)。 -->(-1)^c*(n%5)!*(n/5%5)!*(n/25%5)!...*(3^c)= x (mod 5) -->(-1)^c*(3^(c%4))*(n%5)!*(n/5%5)!*(n/125%5)!... = x(mod 5)。 2,5互质，用CRT合并两个方程组 */ int main(){ cin>>n; if (n==0||n==1){cout<<0<<endl<<1<<endl;return 0;} int64 t=1; for (int i=1;n;n/=5,++i){c+=n/5;t=t*fac(n%5)%5;} if (c&1) t=-t; for (int i=1;i<=c%4;++i) t=t*3%5; t=(t+5)%5; cout<<c<<endl<<t*6%10<<endl; return 0; }
OJ1003是男人下100层
f[i][0],f[i][1]分别代表从底部走到第i块板子左端和右端的最小距离，用线段树单点查询被端点被哪个区间覆盖即可更新答案。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=100015; int n,k; struct Tdata{ int h,l,r; void init(){scanf("%d%d%d",&h,&l,&r);} bool operator <(const Tdata &b)const{return h>b.h;} }data[maxn]; struct Tsegment{ int cov[maxn<<2]; void clear(int p){ if (cov[p]){ cov[p<<1]=cov[p<<1|1]=cov[p]; cov[p]=0; } } void modify(int p,int l,int r,int a,int b,int v){ if (l==a&&r==b){cov[p]=v;return;} clear(p);int mid=(l+r)>>1; if (b<=mid) modify(p<<1,l,mid,a,b,v); else if (a>=mid+1) modify(p<<1|1,mid+1,r,a,b,v); else{modify(p<<1,l,mid,a,mid,v);modify(p<<1|1,mid+1,r,mid+1,b,v);} } int query(int p,int l,int r,int x){ if (cov[p]) return cov[p]; int mid=(l+r)>>1; if (x<=mid) return query(p<<1,l,mid,x); else return query(p<<1|1,mid+1,r,x); } void modify(int l,int r,int v){modify(1,1,1000,l,r,v);} int query(int x){return query(1,1,1000,x);} }seg; void init(){ scanf("%d%d",&n,&k); for (int i=1;i<=n;++i) data[i].init(); sort(data+1,data+n+1); // for (int i=1;i<=n;++i) cout<<data[i].h<<' '<<data[i].l<<' '<<data[i].r<<endl; } int f[maxn][2]; void work(){ memset(f,63,sizeof(f)); seg.modify(data[1].l,data[1].r,1); for (int j,i=2;i<=n;i=j){ for (j=i;j<=n&&data[j].h==data[i].h;++j){ int idx1=seg.query(data[j].l),idx2=seg.query(data[j].r); // cout<<"fuckpp"<<j<<' '<<idx1<<' '<<idx2<<endl; if (data[idx1].h-data[j].h<=k){ if (idx1==1) f[j][0]=data[1].h-data[j].h; else f[j][0]=min(f[idx1][0]+data[j].l-data[idx1].l+data[idx1].h-data[j].h, f[idx1][1]+data[idx1].r-data[j].l+data[idx1].h-data[j].h); } if (data[idx2].h-data[j].h<=k){ if (idx2==1) f[j][1]=data[1].h-data[j].h; else f[j][1]=min(f[idx2][1]+data[idx2].r-data[j].r+data[idx2].h-data[j].h, f[idx2][0]+data[j].r-data[idx2].l+data[idx2].h-data[j].h); } } for (int k=i;k<=j-1;++k) seg.modify(data[k].l,data[k].r,k); } printf("%d ",min(f[n][0],f[n][1])); } int main(){ init(); work(); return 0; }
OJ1004讲笑话
用sum[i]记录前缀和为i的位置数量。
ans=sum[0]+Σsum[i]*(sum[i]-1)/2。
#include<cstdio> #include<iostream> using namespace std; int n,sum[2000015]; int main(){ scanf("%d",&n);int cur=n; for (int x,i=1;i<=n;++i){ scanf("%d",&x); ++sum[cur+=x]; } int res=sum[n]; for (int i=0;i<=2000000;++i) res=(res+1ll*sum[i]*(sum[i]-1)/2)%999999; cout<<res<<endl; return 0; }
OJ1006海岛之桥
最小生成树。
var ans,i,j,n:longint; dis:array[1..100,1..100]of longint; bo:array[1..100]of boolean; procedure mst; var min,mini:longint; lowest:array[1..100]of longint; begin for i:=2 to n do lowest[i]:=maxlongint; lowest[1]:=0; while true do begin min:=maxlongint; for i:=1 to n do begin if (bo[i]) and (lowest[i]<min) then begin min:=lowest[i]; mini:=i; end; end; if min=maxlongint then break; bo[mini]:=false; ans:=ans+min; for i:=1 to n do if (bo[i]) and (dis[mini,i]<lowest[i]) then lowest[i]:=dis[mini,i]; end; end; begin readln(n); for i:=1 to n-1 do for j:=i+1 to n do begin read(dis[i,j]); dis[j,i]:=dis[i,j]; end; fillchar(bo,sizeof(bo),true); mst; writeln(ans); end.
OJ1007[jsoi2008]星球大战
离线处理，利用并查集求连通块数，将删点变为加点。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=1000010; int n,m,k,res,tot,v[maxn],in[maxn],fa[maxn],ans[maxn],now[maxn],pre[maxn],son[maxn],des[maxn]; void Connect(int a,int b){ pre[++tot]=now[a]; now[a]=tot; son[tot]=b; } void Init(){ scanf("%d%d",&n,&m); for (int x,y,i=1;i<=m;++i){ scanf("%d%d",&x,&y); Connect(x,y),Connect(y,x); } scanf("%d",&k); for (int i=1;i<=k;++i){ scanf("%d",&des[i]); v[des[i]]=1; } } int Get(int x){return fa[x]=fa[x]==x?x:Get(fa[x]);} void Put(int x){ ++res; for (int p=now[x];p;p=pre[p]){ int y=son[p]; if (!in[y]) continue; int w=Get(y); if (x!=w) fa[w]=x,--res; } in[x]=1; } void Work(){ for (int i=0;i<n;++i) fa[i]=i; for (int i=0;i<n;++i) if (!v[i]) Put(i); ans[k+1]=res; for (int i=k;i>=1;--i) Put(des[i]),ans[i]=res; for (int i=1;i<=k+1;++i) printf("%d ",ans[i]); } int main(){ Init(); Work(); return 0; }
OJ1009剑圣的逃跑
f[i][j][k]代表当前在(i,j)已使用k次疾风步的最小伤害。
var i,ci,j,k,m,n,q,minn,t:longint; a:array[0..202,0..404]of longint; f:array[0..202,0..404,0..202]of integer; function min(a,b:longint):longint; begin if a>=b then min:=b else min:=a; end; begin readln(n,q); readln(m); for i:=1 to n do begin for j:=1 to i*2-1 do read(a[i,j]); readln; end; fillchar(f,sizeof(f),$7f); f[1,1,1]:=0; f[1,1,0]:=a[1,1]; for i:=1 to n-1 do for j:=1 to i*2-1 do for k:=0 to q do for t:=0 to 2 do f[i+1,j+t,k]:=min(min(f[i+1,j+t,k],f[i,j,k-1]),f[i,j,k]+a[i+1,j+t]); minn:=maxlongint; for i:=1 to n*2-1 do if f[n,i,q]<minn then minn:=f[n,i,q]; if minn>=m then writeln('DEAD') else writeln(m-minn); end.
OJ1011选数
差分约束系统。可以参照：http://ycool.com/post/m2uybbf
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; /* 令sum[i]代表i及之前选了多少个点 对于条件（a，b，c），即可化为 sum[b]-sum[a-1]>=c 还存在条件 sum[i]-sum[i-1]>=0 sum[i]>=0 转化为 sum[b]>=c+sum[a-1]. 比较最长路三角不等式，dis[b]>=dis[a-1]+w(a-1,b)。 于是可以令0点dis=0,并连接0和每个i，边权为0 对于条件（a，b，c），连边（a-1，b，c）。 做最长路即可。 */ const int maxn=100015,maxm=500015; int n,tot,now[maxn],pre[maxm],son[maxm],val[maxm]; void connect(int u,int v,int w){pre[++tot]=now[u];now[u]=tot;son[tot]=v;val[tot]=w;} void init(){ scanf("%d",&n); for (int u,v,w,i=1;i<=n;++i){ scanf("%d%d%d",&u,&v,&w); ++u;++v; connect(u-1,v,w); } for (int i=1;i<=50001;++i){ connect(0,i,0); connect(i,i+1,0); connect(i,i-1,-1); } } /* wa了 好像漏了一个条件 sum[i]-sum[i-1]<=1 即sum[i-1]-sum[i]>=-1 即dis[i-1]>=dis[i]-1 连接(i,i-1,-1)。 */ bool inq[maxn]; int head,tail,q[maxn],dis[maxn]; void spfa(int s){ memset(dis,200,sizeof(dis)); dis[s]=0;q[1]=s;head=0;tail=1;inq[s]=1; while (head!=tail){ if (++head==maxn) head=1; int u=q[head]; for (int p=now[u];p;p=pre[p]) if (dis[son[p]]<dis[u]+val[p]){ dis[son[p]]=dis[u]+val[p]; if (!inq[son[p]]){ if (++tail==maxn) tail=1; q[tail]=son[p];inq[son[p]]=1; } } inq[u]=0; } } void work(){ spfa(0); printf("%d ",dis[50002]); } int main(){ freopen("data11.in","r",stdin); init(); work(); return 0; }
OJ1012酒鬼
DP。f[i][j]代表当前做到前i瓶，上一个没喝的瓶在i-j。
f[i][0]=max(f[i-1][0],f[i-1][1],f[i-1][2])。
f[i][1]=f[i-1][0]+v[i]。
f[i][2]=f[i-1][1]+v[i]。
ans=max(f[n][0],f[n][1],f[n][2])。
var f:array[0..1000,0..2] of longint; i,v:longint; function max(a,b,c:longint):longint; begin if a>b then max:=a else max:=b; if c>max then max:=c; end; begin readln(i); for i:=1 to i do begin readln(v); f[i,0]:=max(f[i-1,0],f[i-1,1],f[i-1,2]); f[i,1]:=f[i-1,0]+v; f[i,2]:=f[i-1,1]+v; end; writeln(max(f[i,0],f[i,1],f[i,2])); end.
OJ1014埃及分数
IDA*：http://blog.csdn.net/u014800748/article/details/47376435。
#include<cstdio> #include<cassert> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxdep=115; typedef long long int64; /* 假设第i-1层的分母为x，剩下的分数和为e/f，i的分母为y，则有 1/x<1/y-->y>x 1/y*(depth-i+1)>e/f-->y<(depth-i+1)*f/e 1/y<e/f->y>f/e max(x,f/e)<y<(depth-i+1)*f/e */ bool got; int64 fmn=1e18,res[maxdep],seq[maxdep]; int64 gcd(int64 a,int64 b){return !b?a:gcd(b,a%b);} void update(int64 seq[],int64 depth){ got=1; if (seq[depth]<fmn){ fmn=seq[depth]; memcpy(res,seq,sizeof(int64)*(depth+1)); } } void dfs(int64 cur,int64 x,int64 e,int64 f,int64 depth){ if (cur==depth){ if (e!=1) return; seq[depth]=f; update(seq,depth); return; } int64 l=x+1,r=(depth-cur+1)*f/e-((depth-cur+1)*f%e==0); for (int64 i=l;i<=r;++i){ seq[cur]=i; int64 nf=f*i,ne=i*e-f,d=gcd(nf,ne); if (ne<=0) continue; dfs(cur+1,i,ne/=d,nf/=d,depth); } } int64 a,b; int main(){ scanf("%I64d%I64d",&a,&b); int64 d=gcd(a,b),depth; for (depth=1,a/=d,b/=d;!got;dfs(1,0,a,b,depth++)); for (int64 i=1;i<depth-1;++i) printf("%I64d ",res[i]); printf("%I64d ",res[depth-1]); } /* ‘以下推导错误..’ 迭代加深搜索，因为状态过多所以bfs无法保存。 因为要求最少数量，考虑枚举深度，并利用dfs空间小的特点来搜索。 假设当前最大深度为depth,第i层的是1/x 对于之后枚举的1/y，满足1/y<1/x,即y>x 还需满足(depth-i)*1/y>a/b-1/x 可推出(depth-i)*1/y>a/b-1/y，（推导错误）。 (depth-i+1)*1/y>a/b 1/y>(a/b)/(depth-i+1)。 y<(depth-i+1)*b/a 所以x<y<(depth-i+1)*b/a */
OJ1015一笔画
对于无向图，笔画数=Σmax(1,每个连通块内奇点数/2)。
拓展：对于有向图，笔画数=Σmax(1,每个连通块内入度-出度为1的点数)。注意要满足连通块内入度-出度为1的点数=连通块内出度-入度为1的点数，否则不知道怎么做...
#include<bits/stdc++.h> using namespace std; const int maxn=1015; int n,m,s; vector<int> g[maxn]; void init(){ scanf("%d%d",&n,&m); for (int u,v,i=1;i<=m;++i){ scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } } bool vis[maxn]; void dfs(int u){ vis[u]=1;if (g[u].size()&1) ++s; for (unsigned int i=0;i<g[u].size();++i) if (!vis[g[u][i]]) dfs(g[u][i]); } void work(){ int res=0; for (int i=1;i<=n;++i) if (!vis[i]&&g[i].size()){ s=0;dfs(i); res+=max(1,s>>1); } printf("%d ",res); } int main(){ init(); work(); return 0; }
OJ1017技能树
递推。
f[i][j]代表节点数为i个高度为j的满足条件的二叉树有多少颗
g[i][j]代表节点数为i个高度<=j的满足条件的二叉树有多少颗
f[i][j]=sigma(2*f[k][j-1]*g[i-1-k][j-1]-f[k][j-1]*f[i-1-k][j-1])。
#include<iostream> using namespace std; const int mod=9901; int n,m,f[315][115],g[315][115]; /* f[i][j]代表节点数为i个高度为j的满足条件的二叉树有多少颗 g[i][j]代表节点数为i个高度<=j的满足条件的二叉树有多少颗 f[i][j]=sigma(2*f[k][j-1]*g[i-1-k][j-1]-f[k][j-1]*f[i-1-k][j-1])。 */ int main(){ cin>>n>>m; f[1][1]=g[1][1]=1; for (int j=2;j<=m;++j) for (int i=1;i<=n;++i){ for (int k=1;k<=i-1;++k) f[i][j]=(1ll*f[i][j]+2ll*f[k][j-1]*g[i-1-k][j-1]%mod-1ll*f[k][j-1]*f[i-1-k][j-1]%mod+mod)%mod; g[i][j]=(g[i][j-1]+f[i][j])%mod; } cout<<f[n][m]<<endl; return 0; }
OJ1019观光游览
DP。
f[i][j]代表前i个格子安排j个人（最后一个人管到i）所能得到的最大权值
f[i][j]=max(f[k-1][j-1]+w(k,i)).
现在考虑w(j,i)怎么求，即被[j,i]完全覆盖的景点权值和。
区间[a,b]被完全覆盖，满足 a>=k且b<=i
数据范围较小，用二维前缀和即可。 查询sum(k,1,m,i)。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=115; /* f[i][j]代表前i个格子安排j个人（最后一个人管到i）所能得到的最大权值 f[i][j]=max(f[k-1][j-1]+w(k,i)). 现在考虑w(j,i)怎么求，即被[j,i]完全覆盖的景点权值和。 区间[a,b]被完全覆盖，满足 a>=k且b<=i 数据范围较小，用二维前缀和即可。 查询sum(k,1,m,i)。 */ int m,n,k,sum[maxn][maxn],f[maxn][maxn]; int get_sum(int x1,int y1,int x2,int y2){return sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1];} void init(){ scanf("%d%d",&m,&n); for (int x,y,v,i=1;i<=n;++i){ scanf("%d%d%d",&x,&y,&v); sum[x][y]+=v; } scanf("%d",&k); } void work(){ for (int i=1;i<=m;++i) for (int j=1;j<=m;++j) sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; memset(f,200,sizeof(f)); f[0][0]=0; for (int i=1;i<=m;++i) for (int j=1;j<=k;++j) for (int l=1;l<=i;++l) f[i][j]=max(f[i][j],f[l-1][j-1]+get_sum(l,1,m,i)); printf("%d ",f[m][k]); } int main(){ init(); work(); return 0; }
OJ1021谣言的传播
floyd。求出全源最短路后枚举起始点更新答案即可。
var min,mini,n,i,j,k,m,max:longint; g:array[1..100,1..100]of longint; dist:array[1..100,1..100]of longint; begin readln(n); fillchar(g,sizeof(g),$7f); for i:=1 to n do begin read(m); for j:=1 to m do read(k,g[i,k]); readln; end; for k:=1 to n do for i:=1 to n do if g[i,k]<>2139062143 then for j:=1 to n do if g[k,j]<>2139062143 then if g[i,j]>g[i,k]+g[k,j] then g[i,j]:=g[i,k]+g[k,j]; min:=maxlongint; for i:=1 to n do begin max:=-2139062143; for j:=1 to n do if i<>j then if g[i,j]>max then max:=g[i,j]; if max<min then begin min:=max; mini:=i; end; end; if min=2139062143 then writeln('disjoint') else writeln(mini,' ',min); readln; end.
OJ1023奖金
拓扑排序DP。f[i]代表i最小工资。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=10010,maxm=20010; int n,m,tot,ind[maxn],f[maxn],now[maxn],pre[maxm],son[maxm]; void connect(int u,int v){ pre[++tot]=now[u]; now[u]=tot; son[tot]=v; ind[v]++; } void read(int &x){ char ch; for (ch=getchar();!isdigit(ch);ch=getchar()); for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar()); } void init(){ read(n),read(m); for (int i=1,u,v;i<=m;++i){ read(u),read(v); connect(v,u); } } int q[maxn]; bool vis[maxn]; void top(int st){ int head=0,tail=1; f[st]=100,q[1]=st,vis[st]=1; while (head!=tail){ int u=q[++head]; for (int p=now[u];p;p=pre[p]){ f[son[p]]=max(f[u]+1,f[son[p]]); if (!--ind[son[p]]) q[++tail]=son[p],vis[son[p]]=1; } } } void work(){ for (int i=1;i<=n;++i) if (!ind[i]&&!vis[i]) top(i); for (int i=1;i<=n;++i) if (!vis[i]){ puts("Poor Xed"); return; } int ans=0; for (int i=1;i<=n;++i) ans+=f[i]; printf("%d ",ans); } int main(){ init(); work(); return 0; }
OJ1025魔法书
背包。f[i]代表话费i的时间所能得到的最大获益。显然a[i]小的更划算，所以按降序排序即可背包。
program q1025; var f:array[0..1000000] of longint; bt:array[0..300] of longint; t:array[0..300] of longint; bo,v:array[0..300,-1..300] of longint; n,i,j,m,p,b,c,k:longint; procedure swap(var a,b:longint); var t:longint; begin t:=a; a:=b; b:=t; end; procedure qsort(l,r,k: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=bo[k][(l+r) div 2]; repeat while bo[k,i]<x do inc(i); while x<bo[k,j] do dec(j); if not(i>j) then begin swap(bo[k,i],bo[k,j]); inc(i); j:=j-1; end; until i>j; if l<j then qsort(l,j,k); if i<r then qsort(i,r,k); end; function max(a,b:longint):longint; begin if a>b then exit(a); exit(b); end; begin readln(n,m,p); for i:=1 to m do read(bo[i][0]); readln; for i:=1 to n do begin readln(b,c); inc(bo[c][-1]); bo[c][bo[c,-1]]:=b; end; for i:=1 to m do qsort(1,bo[i][-1],i); for i:=1 to m do for j:=1 to bo[i,-1] do begin bo[i,j]:=bo[i,j]+bo[i,j-1]; v[i,j]:=v[i,j-1]+1; end; for i:=1 to n do for j:=p downto 0 do for k:=1 to bo[i,-1] do if j>=bo[i,k] then f[j]:=max(f[j],f[j-bo[i,k]]+v[i,k]); writeln(f[p]); end.
OJ1027[Usaco2008 Jan]无线电通讯塔
树形DP。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=50010,maxm=100010,inf=(int)1e8; int n,tot,now[maxn],pre[maxm],son[maxm]; void connect(int u,int v){ pre[++tot]=now[u]; now[u]=tot; son[tot]=v; } void read(int &x){ char ch; for (ch=getchar();!isdigit(ch);ch=getchar()); for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar()); } void init(){ read(n); for (int i=1,u,v;i<=n-1;++i){ read(u),read(v); connect(u,v),connect(v,u); } } int f[maxn][3]; void dfs(int u,int fa){ int sum=0; f[u][1]=1,f[u][0]=inf;; for (int p=now[u];p;p=pre[p]){ if (son[p]==fa) continue; dfs(son[p],u); f[u][2]+=f[son[p]][0]; f[u][1]+=min(f[son[p]][0],min(f[son[p]][1],f[son[p]][2])); sum+=min(f[son[p]][0],f[son[p]][1]); } for (int p=now[u];p;p=pre[p]){ if (son[p]==fa) continue; f[u][0]=min(f[u][0],sum+f[son[p]][1]-min(f[son[p]][0],f[son[p]][1])); } } void work(){ dfs(1,0); printf("%d ",min(f[1][0],f[1][1])); } int main(){ init(); work(); return 0; }
OJ1034电梯
背包。
#include<iostream> #include<cstdio> using namespace std; int max(int a,int b){ if (a>b) return a; return b; } int main(){ int w,n,ans=0; int m[10000],age[10000],f[10000]; cin>>w>>n; for (int i=0;i<n;++i) cin>>m[i]; for (int i=0;i<n;++i){ cin>>age[i]; ans+=age[i]; } memset(f,0,sizeof(f)); for (int i=0;i<n;++i) for (int j=w;j>=m[i];--j) f[j]=max(f[j],f[j-m[i]]+age[i]); ans-=f[w]; cout<<ans<<endl; //system("pause"); return 0; }
OJ1035生日蛋糕
背包。注意在重量最大的前提下要求出最小蛋糕数。
f[i].w，f[i][j].n,代表在总重量在模n意义下=i的最大重量，和在此前提下的最少数目。
var n , m , i , j , k : longint; a: array[ 1 .. 2000 ] of longint; b , bb : array[ 0 .. 10000 ] of boolean; f , ff , p , pp: array[ 0 .. 10000 ] of longint; begin readln( n , m ); for i := 1 to m do readln( a[ i ] ); b[ 0 ] := true; for i := 1 to m do begin for j := n - 1 downto 0 do if b[ j ] then begin bb[ j ] := true; bb[ ( j + a[ i ] ) mod n ] := true; if ( f[ ( j + a[ i ] ) mod n ] < f[ j ] + a[ i ] ) or ( f[ ( j + a[ i ] ) mod n ] = f[ j ] + a[ i ] ) and ( p[ ( j + a[ i ] ) mod n ] > p[ j ] + 1 ) then begin ff[ ( j + a[ i ] ) mod n ] := f[ j ] + a[ i ]; pp[ ( j + a[ i ] ) mod n ] := p[ j ] + 1; end; end; b := bb; f := ff; p := pp; end; if p[ 0 ] > 0 then writeln( f[ 0 ] , ' ' , p[ 0 ] ) else writeln( 'no answer' ); end.
待更新。