【USACO】DP動態規劃小測（一），usacodp動態規劃
｛20160927 19:30~21:30｝
總分400分，我113.33，穩穩地墊底了......（十分呼應我上面的博客名，hhh~）過了這麼多天我才打完所有代碼，廢話我也就不多說了。不過，雖然時間花費的多，但我覺得我的PG也是“博采眾長”了。
-------------------------------------------------------------------------------------------------------------------------------------------------
T1 接住蘋果(bcatch)
題意：有2顆蘋果樹，有K次移動機會，問最多能接到的蘋果數。
解法：可以用f[i][j][2]或f[i][j]和g[i][j]來實現，表示掉了i個蘋果，移動j次的最大值。也可以利用j的奇偶直接判斷當前在的樹，進而進行+1或0。
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6
7 const int N=1010,K=35;
8 int f[N][K],g[N][K],a[N];
9
10 int mmax(int x,int y)
11 { return x>y?x:y; }
12
13 int main()
14 {
15 //freopen("bcatch.in","r",stdin);
16 //freopen("bcatch.out","w",stdout);
17 int n,k;
18 scanf("%d%d",&n,&k);
19 for (int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]--;
20 int x,y,ans=0;
21 memset(f,0,sizeof(f));
22 memset(g,0,sizeof(g));
23 for (int i=1;i<=n;i++)
24 for (int j=0;j<=k;j++)
25 {
26 x=1-a[i],y=1-x;
27 f[i][j]=x+f[i-1][j],g[i][j]=y+g[i-1][j];
28 if (j>0)
29 {
30 f[i][j]=mmax(f[i][j],x+g[i-1][j-1]);
31 g[i][j]=mmax(g[i][j],y+f[i-1][j-1]);
32 }
33 if (i==n) ans=mmax(ans,mmax(f[i][j],g[i][j]));
34 }
35 printf("%d\n",ans);
36 return 0;
37 }
View Code
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2 滑雪課程(ski)
題意：有N個雪坡和S個課程。雪坡需要耗費一定的時間，且有技能點要求，課程也需要耗費一定的時間，但可以進修到一定的技能點數。問在時間T內最多能滑多少次雪坡。
有兩種解法：（時間和內存哪種更優就看數據范圍了~）
1.f[i][j]表示前i的時間內能力為j時能滑雪的最大次數，預處理一下p[i]為當能力為i時能花的所有雪坡中耗費時間最小的。每次分別用f[i][j]更新現在有課上便上課，和滑一次雪的狀態。
注意——邊界條件；只有當前狀態存在（不為-1）才可拓展到其他的狀態；f[i][j]除了更新上課或滑雪的，也要更新到f[i+1][j]。
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7
8 const int T=(int)1e4+10,S=110,N=(int)1e5+10,C=100;
9 int f[T][C],p[C+10];
10 struct node{int c,d;}a[N];
11 struct hy{int m,l,c;}b[S];
12
13 bool cmp(hy x,hy y) {return x.m<y.m;}
14 void upd(int &x,int y) {x=x>y?x:y;}
15 void upd2(int &x,int y) {x=x<y?x:y;}
16 int mabs(int x) {return x>0?x:-x;}
17
18 int main()
19 {
20 //freopen("ski.in","r",stdin);
21 //freopen("ski.out","w",stdout);
22 int t,s,n;
23 scanf("%d%d%d",&t,&s,&n);
24 for (int i=1;i<=s;i++)
25 scanf("%d%d%d",&b[i].m,&b[i].l,&b[i].c);
26 sort(b,b+1+s,cmp);
27 for (int i=1;i<=n;i++)
28 scanf("%d%d",&a[i].c,&a[i].d);
29 memset(p,63,sizeof(p));
30 for (int i=1;i<=n;i++)
31 upd2(p[a[i].c],a[i].d);
32 for (int i=1;i<=C;i++)
33 upd2(p[i],p[i-1]);
34 int tmp=1,ans=0;
35 memset(f,-1,sizeof(f));
36 f[0][1]=0;
37 for (int i=0;i<=t;i++)
38 {
39 for (int j=1;j<=C;j++)
40 {
41 if (f[i][j]<0) continue;//
42 upd(f[i+1][j],f[i][j]);
43 upd(f[i+p[j]][j],f[i][j]+1);
44 while (b[tmp].m==i && tmp<=s && i+b[tmp].l<=t)
45 upd(f[i+b[tmp].l][b[tmp].c],f[i][j]), tmp++;
46 if (i==t) upd(ans,f[i][j]);
47 }
48 }
49 printf("%d\n",ans);
50 return 0;
51 }
View Code 1
2.f[i]表示上了第i節課能滑雪的最大次數，預處理同上。每次f[i]存枚舉上一次上了哪節課，而到這節課的時間裡滑雪或上課的最佳答案。
注意——邊界條件；添加時間為0和時間為t的課程，保證“有始有終”。
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7
8 const int T=(int)1e4+10,S=110,N=(int)1e5+10,C=100;
9 int f[S],p[C+10];
10 struct node{int c,d;}a[N];
11 struct hy{int m,l,c;}b[S];
12
13 //bool cmp(hy x,hy y) {return x.m<y.m;}
14 void upd(int &x,int y) {x=x>y?x:y;}
15 void upd2(int &x,int y) {x=x<y?x:y;}
16 int mabs(int x) {return x>0?x:-x;}
17
18 int main()
19 {
20 //freopen("ski.in","r",stdin);
21 //freopen("ski.out","w",stdout);
22 int t,s,n,ans=0;
23 scanf("%d%d%d",&t,&s,&n);
24 for (int i=1;i<=s;i++)
25 scanf("%d%d%d",&b[i].m,&b[i].l,&b[i].c);
26 b[0].m=0,b[0].l=0,b[0].c=1;
27 b[++s].m=t;//add terminal
28 //sort(b,b+1+s,cmp);//無須排序
29 for (int i=1;i<=n;i++)
30 scanf("%d%d",&a[i].c,&a[i].d);
31 memset(p,63,sizeof(p));
32 for (int i=1;i<=n;i++)
33 upd2(p[a[i].c],a[i].d);
34 for (int i=1;i<=C;i++)
35 upd2(p[i],p[i-1]);
36 memset(f,-1,sizeof(f));
37 f[0]=0;
38 for (int i=1;i<=s;i++)
39 {
40 if (b[i].l+b[i].m>t) continue;//
41 for (int j=0;j<i;j++)
42 if (f[j]>=0 && b[i].m>=b[j].m+b[j].l)//
43 upd(f[i],f[j]+mabs(b[i].m-b[j].m-b[j].l)/p[b[j].c]);
44 upd(ans,f[i]);
45 }
46 printf("%d\n",ans);
47 return 0;
48 }
View Code 2
--------------------------------------------------------------------------------------------------------------------------------------------------
T3 滑雪比賽(bobsled)
題意：初始速度為1，有N個限制速度大小的彎道，給出與起點的距離，問L內最大能達到的速度。
解法：先貪心——從後往前掃一遍來保證各彎道間的限制速度可以互相到達，因為速度有後效性(?)，便直接保證了不用比較下一個的限制速度，還擔心降不到下一個的限制速度。
接著保存每到一個彎道後的速度與距離，進而根據與下一個彎道的速度曲線的單調性（遞增(多)---遞減(少)、遞增、遞增(少)---遞減(多)、遞減）來算出其間的最大值，和到下一個彎道的速度。P.S.畫圖輔助會清晰一點。
注意——終點也可看成一個“彎道”，而沒有限制速度。
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7
8 const int L=(int)1e9+10,N=(int)1e5+10;
9 struct node{int t,v;}
10 a[N];
11
12 bool cmp(node x,node y)
13 {
14 if (x.t!=y.t) return x.t<y.t;
15 return x.v<y.v;
16 }
17 int mmax(int x,int y)
18 { return x>y?x:y; }
19 int mmin(int x,int y)
20 { return x<y?x:y; }
21 int main()
22 {
23 //freopen("bobsled.in","r",stdin);
24 //freopen("bobsled.out","w",stdout);
25 int l,n;
26 scanf("%d%d",&l,&n);
27 for (int i=1;i<=n;i++)
28 scanf("%d%d",&a[i].t,&a[i].v);
29 sort(a+1,a+1+n,cmp);
30 int p=0;a[0].t=-1;
31 for (int i=1;i<=n;i++)
32 if (a[i].t!=a[i-1].t) a[++p]=a[i];
33 n=p;
34 for (int i=n-1;i>=1;i--)
35 a[i].v=mmin(a[i].v,a[i+1].v+(a[i+1].t-a[i].t));
36 int t=0,v=1;//now
37 int x,ans=0;
38 for (int i=1;i<=n;i++)
39 {
40 if (a[i].v>v)
41 {
42 if (a[i].t-t>=a[i].v-v)//=
43 x=a[i].v+((a[i].t-t)-(a[i].v-v))/2,v=a[i].v;
44 else x=v+(a[i].t-t),v=x;
45 ans=mmax(ans,x);
46 }
47 else
48 {
49 x=v+((a[i].t-t)-(v-a[i].v))/2;
50 v=a[i].v;
51 ans=mmax(ans,x);
52 }
53 t=a[i].t;
54 }
55 ans=mmax(ans,v+(l-t));
56 printf("%d\n",ans);
57 return 0;
58 }
View Code
--------------------------------------------------------------------------------------------------------------------------------------------------
T4 奶牛飛盤隊(fristeam)
題意：有N頭有一定能力的奶牛，問選出能力和為M的倍數的方案總數。
解法：要想到把%M的值作為DP數組的一個維度。f[i][j]表示在前i頭奶牛中選到的能力和%M為j的方案數，這樣每次只需分別選或不選當前第i頭奶牛，由f[i-1]的狀態推出。
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6
7 const int N=2010,M=1010,mod=(int)1e8;
8 int a[N],f[N][M];
9
10 int main()
11 {
12 //freopen("fristeam.in","r",stdin);
13 //freopen("fristeam.out","w",stdout);
14 int n,m;
15 scanf("%d%d",&n,&m);
16 for (int i=1;i<=n;i++)
17 scanf("%d",&a[i]),a[i]%=m;
18 for (int j=1;j<m;j++) f[0][j]=0;
19 f[0][0]=1;
20 for (int i=1;i<=n;i++)
21 for (int j=0;j<m;j++)
22 {
23 int x=j-a[i];
24 if (x<0) x+=m;
25 f[i][j]=(f[i-1][j]+f[i-1][x])%mod;
26 }
27 printf("%d\n",f[n][0]-1);
28 return 0;
29 }
View Code
