【USACO】DP动态规划小测(一)

2018-06-17 23:42:43来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

{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,因为初始f[0][0]=1是为了方便计算,而实际为0的。

 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

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:A -- HDU 4585 Shaolin

下一篇:初学C++ 之 auto关键字(IDE:VS2013)