E. Kojiro and Furrari
题意说的是 在一条直线上 有n个加油站， 每加一单位体积的汽油 可以走1km 然后每个加油站只有一种类型的汽油，汽油的种类有3种 求从起点出发到达终点要求使用最少的 1 号汽油的前提下使用最少的二号汽油，
我们可以这样考虑
当前在第i个加油站的时候 i个加油站 有3种情况
第一种 他是只有 1 号汽油 那么他必须携带 尽量少的 1号汽油到达离他最近的2号汽油点或者3号汽油点 更新这个点到达终点的代价 取最小值，因为他必须通过那个点到达其他点
第二种 他只有 2 号汽油， 那么他必须携带 尽量多的 2号汽油到达能达到的最远的1号汽油点，这样可以更少使用1号汽油，或者 带尽量少的汽油到达离他最近的3号汽油的点，或者最近的2号汽油的点
第三种 如果他是3号汽油 那么他必须携带尽量少的3号汽油到达离他最近的点，或者带尽量多的3号汽油到达离他能达到的最远的1 、2号汽油点
#include <iostream> #include <algorithm> #include <cstdio> #include <string.h> #include <vector> using namespace std; typedef long long LL; const int maxn=200005; const int INF=2147483647; struct point{ int x,t; point(int cx=0, int ct=0){ x=cx; t=ct; } bool operator <(const point &rhs)const{ return x<rhs.x; } }P[maxn]; int D[4][maxn],num[4]; int dp[maxn][3]; int e,s,n,m; int bitlook1(int x,int *C, int n) { int L=0,R=n-1,ans=-1; while(L<=R) { int mid=(L+R)>>1; int id=C[mid]; if( P[id].x>=x ){ ans=mid; R=mid-1; }else{ L=mid+1; } } return ans; } void cmp(int &A, int &B,int &V, int C, int D, int DV) { if(A>=C){ if(A==C){ if(B<D) return ; if(B>D){ B=D; V=DV; }else{ V=min(V,DV); } } else { A=C; B=D; V=DV; } } } void solve1(int id) { int loc=P[id].x; int d1=bitlook1(loc+1,D[1],num[1]); int d2=bitlook1(loc+1,D[2],num[2]); int d3=bitlook1(loc+1,D[3],num[3]); if(d3!=-1)d3=D[3][d3]; if(d2!=-1)d2=D[2][d2]; if(d1!=-1)d1=D[1][d1]; if( d3!=-1 && P[d3].x <= loc+s ) { int cp1 = dp[d3][1]+P[d3].x-loc; int cp2 = dp[d3][2]; cmp(dp[id][1],dp[id][2],dp[id][0],cp1,cp2,P[d3].x-loc); } if(d2!=-1 && P[d2].x<=loc+s) { int cp1 = dp[d2][1]+P[d2].x-loc; int cp2 = dp[d2][2]; cmp(dp[id][1],dp[id][2],dp[id][0],cp1,cp2,P[d2].x-loc); } if( d1!=-1 && P[d1].x<=loc+s) { int cp1 = dp[d1][1]+P[d1].x-loc; int cp2 = dp[d1][2]; cmp(dp[id][1],dp[id][2],dp[id][0],cp1,cp2,P[d1].x-loc); } } int bitlook2(int x,int *C, int n) { int L=0,R=n-1,ans=-1; while(L<=R) { int mid=(L+R)>>1; int id=C[mid]; if( P[id].x<=x ){ ans=mid; L=mid+1; }else{ R=mid-1; } } return ans; } void solve2(int id) { int loc=P[id].x; int d1=bitlook2(loc+s,D[1],num[1]); int d2=bitlook1(loc+1,D[2],num[2]); int d3=bitlook1(loc+1,D[3],num[3]); if(d3!=-1)d3=D[3][d3]; if(d2!=-1)d2=D[2][d2]; if(d1!=-1)d1=D[1][d1]; if( d3!=-1 && P[d3].x <= loc+s ) { int cp1 = dp[d3][1]; int cp2 = dp[d3][2]+P[d3].x-loc; cmp(dp[id][1],dp[id][2],dp[id][0],cp1,cp2,P[d3].x-loc); } if(d2!=-1 && P[d2].x<=loc+s) { int cp1 = dp[d2][1]; int cp2 = dp[d2][2]+P[d2].x-loc; cmp(dp[id][1],dp[id][2],dp[id][0],cp1,cp2,P[d3].x-loc); } if( d1!=-1&&P[d1].x>loc) { int cp0=s; int lit = s-(P[d1].x-loc); int cp1 = dp[d1][1]-min(lit,dp[d1][0]); int cp2 = dp[d1][2]+cp0; cmp(dp[id][1],dp[id][2],dp[id][0],cp1,cp2,cp0); } } void solve3(int id) { int loc=P[id].x; int d1=bitlook2(loc+s,D[1],num[1]); int d2=bitlook2(loc+s,D[2],num[2]); int d3=bitlook1(loc+1,D[3],num[3]); if(d3!=-1)d3=D[3][d3]; if(d2!=-1)d2=D[2][d2]; if(d1!=-1)d1=D[1][d1]; if( d3!=-1 && P[d3].x<=loc+s ) { cmp(dp[id][1],dp[id][2],dp[id][0],dp[d3][1],dp[d3][2],0); } if(d2!=-1&&P[d2].x>loc) { int lit = s-(P[d2].x-loc); int cp1 = dp[d2][1]; int cp2 = dp[d2][2]-min(dp[d2][0],lit); cmp(dp[id][1],dp[id][2],dp[id][0],cp1,cp2,0); } if(d1!=-1&&P[d1].x>loc) { int lit = s-(P[d1].x-loc); int cp1 = dp[d1][1]-min(dp[d1][0],lit); int cp2 = dp[d1][2]; cmp(dp[id][1],dp[id][2],dp[id][0],cp1,cp2,0); } } void solve4(int loc, int &S1,int &S2) { int k; int d1=bitlook2(loc+s,D[1],num[1]); int d2=bitlook2(loc+s,D[2],num[2]); int d3=bitlook1(loc+1,D[3],num[3]); if(d3!=-1)d3=D[3][d3]; if(d2!=-1)d2=D[2][d2]; if(d1!=-1)d1=D[1][d1]; if( d3!=-1 && P[d3].x<=loc+s &&dp[d3][1]!=INF) { cmp(S1,S2,k,dp[d3][1],dp[d3][2],0); } if(d2!=-1&&P[d2].x>loc&&dp[d2][1]!=INF) { int lit = s-(P[d2].x-loc); int cp1 = dp[d2][1]; int cp2 = dp[d2][2]-min(dp[d2][0],lit); cmp(S1,S2,k,cp1,cp2,0); } if(d1!=-1&&P[d1].x>loc&&dp[d1][1]!=INF) { int lit = s-(P[d1].x-loc); int cp1 = dp[d1][1]-min(dp[d1][0],lit); int cp2 = dp[d1][2]; cmp(S1,S2,k,cp1,cp2,0); } } int main() { while(scanf("%d%d%d%d",&e,&s,&n,&m)==4) { num[0]=num[1]=num[2]=num[3]=0; int k=0; for(int i=0; i<n; i++) { scanf("%d%d",&P[k].t,&P[k].x); if(P[k].x<e)k++; } n=k; sort(P,P+n); if(P[n-1].x!=e) { P[n]=point(e,3); n++; } for(int i=0; i<n; i++) if(P[i].t==1) D[ 1 ][num[1]++ ] =i; else if(P[i].t==2) D[2][ num[2] ++ ]=i; else D[3][ num[3]++ ]=i; dp[n-1][0]=dp[n-1][1]=dp[n-1][2]=0; for(int i=n-2; i>=0;i--)dp[i][0]=dp[i][1]=dp[i][2]=INF; for(int i=n-2; i>=0; i--) { if(P[i].t==1)solve1(i); else if(P[i].t==2)solve2(i); else solve3(i); if(dp[i][1]==INF)break; } for(int i=0;i<m; i++) { int S1=INF,S2=INF; int loc; scanf("%d",&loc); solve4(loc,S1,S2); if(S1==INF){ printf("-1 -1 "); }else{ printf("%d %d ",S1,S2); } } } return 0; } /* 386 20 1 1 2 369 351 */
F. Zublicanes and Mumocrates 树形dp
题意给了一棵树 要求使得这棵树所有的节点分为两个阵营，其中叶子节点要均分，求最少的两个阵营相邻， 也就是求 最少的边使得 这些边两头阵营不同
dp[cur][i][j] 表示当cur为i阵营的时候 有j个和i同阵营的方案
dp[cur][i][j+k] = min{dp[to][i^1][j=(叶子个数-d)]+dp[cur][i][k]+1,dp[to][i][j]+dp[cur][i][k]}
cnt为叶子节点的个数 最后答案是 min{ dp[root][0][cnt/2] ,dp[root][1][cnt/2]}
#include <algorithm> #include <string.h> #include <cstdio> #include <iostream> using namespace std; const int maxn=5005; int H[maxn],to[maxn*2],nx[maxn*2],numofE; void add(int u, int v) { numofE++; to[numofE]=v; nx[numofE]=H[u]; H[u]=numofE; } int dp[maxn][2][maxn]; int dp2[2][maxn],sz[maxn]; int d[maxn]; void dfs(int cur ,int per) { if(d[cur]==1){ sz[cur]=1; dp[cur][0][1]=dp[cur][1][1]=0; return ; } dp[cur][0][0]=dp[cur][1][0]=0; for(int i=H[cur]; i ; i=nx[i]) { int tto = to[i]; if(tto==per)continue; dfs(tto,cur); for(int i=0; i<=sz[cur]; i++) for(int u=0; u<2; u++) { if( dp[cur][u][i] == -1 ) continue; for(int j=0; j<=sz[tto]; j++) for(int v=0; v<2; v++) { if(dp[tto][v][j]==-1)continue; if(u==v) { if(dp2[u][i+j]==-1) { int k=dp[cur][u][i]+dp[tto][v][j]; dp2[u][i+j] = k; }else { int k=min(dp[cur][u][i]+dp[tto][v][j],dp2[u][i+j]); dp2[u][i+j]=k; } }else { int nu=sz[tto]; if(dp2[u][i+nu-j]==-1) { int k=dp[cur][u][i]+dp[tto][v][j]+1; dp2[u][i+nu-j]=k; } else { int k=min(dp[cur][u][i]+dp[tto][v][j]+1,dp2[u][i+nu-j]); dp2[u][i+nu-j]=k; } } } } sz[cur]+=sz[tto]; for(int i=0; i<=sz[cur]; i++) for(int j=0; j<2; j++) { dp[cur][j][i]=dp2[j][i]; dp2[j][i]=-1; } } } int main() { int n; while(scanf("%d",&n)==1) { memset(d,0,sizeof(d)); memset(dp,-1,sizeof(dp)); memset(sz,0,sizeof(sz)); memset(dp2,-1,sizeof(dp2)); memset(H,0,sizeof(H)); numofE=0; for(int i=1; i<n; i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); d[a]++;d[b]++; } if(n==2){ printf("%d ",1); continue; } int root; int cnt=0; for(int i=1; i<=n; i++){ if(d[i]==1)cnt++; else root=i; } dfs(root,-1); printf("%d ",min(dp[root][0][cnt/2],dp[root][1][cnt/2])); } return 0; } /* 6 1 2 2 5 2 3 3 4 3 6 */