NOIp 2014飞扬的小鸟【dp】By cellur925

时间:2022-12-16 15:31:13

题目传送门

放在14年Day1T3的dp题目...应该比较看出来是dp算法吧,因为在本蒟蒻看来求最值的算法不清晰时就是dp了==。

状态还是比较好设计的,考虑到每个情况需要记录下的量:f[i][j]表示横坐标到达i,纵坐标到达j的最小点击次数。

转移的话,也不难想,当前有两种转移方法:不点,小鸟会掉一定高度;点q次,小鸟会上升一定高度。(注意是可以连续点很多次的)

  也就能写出转移:f[i][j]=min(f[i][j],f[i-1][j-q*x[i]]+q,f[i-1][j+y[i]]),复杂度O(n*m*q),TLE。另外 开始看这个方程的时候,直观上感觉因为x[i]是增量,y[i]是减量,这个方程的符号是不是写反了?后来冷静分析一下会发现,f数组中的第二维记录的是当前的高度,因为在前一个坐标点屏幕了,所以前一个坐标会比当前低,+y[i]同理。

  我们考虑一下优化,状态好像不能再优化了,考虑转移优化。n*m的复杂度貌似才能卡都不能去掉的样子,枚举每次点的次数就很让人头大。考虑从这里出发进行优化,会不会我们多枚举了很多重复的东西。

  来自一位dalao的blog我们可以借鉴使用模拟转移法。比如x[i]=3,我们现在要转移f[3][],10位第二维上限。根据我们开始写的转移方程:

  f[3][10]=min(f[2][7]+1,f[2][4]+2,f[2][1]+3)

  f[3][7]=min(f[2][4]+1,f[2][1]+2)

  f[3][4]=min(f[2][1])

  果不其然很多重复的枚举==!我么在f[3][7]转移时,其实实际用f[i-1][j-x[i]]+1和f[i][j-1]+1来转移即可,这样就省去了那个q的复杂度。

剩下的就是一些细节问题了。

  虽说是游戏题而且每年都有一道游戏题,即使对那个现实中的游戏非常熟悉,玩的非常好也要注意一下题目背景下的游戏规则==!(比如这题我有一段时间一直玩flappybird==)在本题中,小鸟到天花板上是不会判输的,这一点比较容易忽视。

  “小鸟从游戏界面最左边任意整数高度位置出发”,这是赋初值的依据。

  “输入数据保证 P 各不相同,但不保证按照大小顺序给出”,所以输进来管道信息后要排序。

  如果当前我们选择了下降,那我们就不能再点屏幕了,所以我们先把点屏幕的情况处理掉。(分开处理)

  还有到管道的时候符不符合要求。

Code

NOIp 2014飞扬的小鸟【dp】By cellur925NOIp 2014飞扬的小鸟【dp】By cellur925
 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 int n,m,k,pos=1,fake,ans=0x7fffffff;
 8 int x[10090],y[10090];
 9 int f[10090][1090];
10 struct tube{
11     int p,l,h;
12 }tu[1090];
13 
14 bool cmp(tube a,tube b)
15 {
16     return a.p<b.p;
17 }
18 
19 int main()
20 {
21     scanf("%d%d%d",&n,&m,&k);
22     for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
23     for(int i=1;i<=k;i++)//记录管道 
24         scanf("%d%d%d",&tu[i].p,&tu[i].l,&tu[i].h);
25     sort(tu+1,tu+1+k,cmp);//根据左端点排序
26     memset(f,127,sizeof(f));
27     for(int i=0;i<=m;i++) f[0][i]=0;//最左边开始地点不定 
28     for(int i=1;i<=n;i++)
29     {
30         if(tu[pos].p==i)//现在到管道了 
31         {// 不能碰到管道 所以小于 
32             for(int j=1;j<tu[pos].h;j++)
33             //由于状态中f[i][j]中j是当前高度,所以之前高度是减去x[i] 
34                 if(j-x[i]>0)
35                 //玄学优化终于看懂了==
36                 //然后要下课了qwq 
37                     f[i][j]=min(f[i][j],min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1));
38             //每次只会向下掉一次 所以单独处理 
39             for(int j=1;j<tu[pos].h;j++)
40                 if(j+y[i]<=m&&j>tu[pos].l)
41                 //在管道底之上,在天花板之下 
42                     f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
43             bool flag=0;
44             for(int j=1;j<tu[pos].h;j++)
45             {//在管道底之上,在天花板之下
46                 if(j<=tu[pos].l) f[i][j]=1e8;
47                 if(f[i][j]<1e7) flag=1;
48             }
49             if(!flag)
50             {
51                 printf("0\n%d",pos-1);
52                 return 0;
53             }
54             pos++;//这一句容易忘掉== 
55         }
56         else
57         {
58             for(int j=1;j<=m;j++)
59                 if(j-x[i]>0)
60                     f[i][j]=min(f[i][j],min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1));
61             for(int j=1;j<=m;j++)
62                 if(j+y[i]<=m)
63                     f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
64             //天花板上死不掉 但是可以继续跳 
65             //对于天花板的处理。无论在j范围内的哪个位置跳一步都会到顶 
66             for(int j=m-x[i];j<=m;j++)// 跳一步   跳2步 
67                 f[i][m]=min(f[i][m],min(f[i][j]+1,f[i-1][j]+1));
68         }
69     }
70     //遍历所有情况找最优解 
71     for(int i=1;i<=m;i++)
72         ans=min(ans,f[n][i]);//这个取最优解的方法貌似很可取的样子== 
73     printf("1\n%d",ans);
74     return 0;
75 }
With notes
NOIp 2014飞扬的小鸟【dp】By cellur925NOIp 2014飞扬的小鸟【dp】By cellur925
 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 int n,m,k,pos=1,fake,ans=0x7fffffff;
 8 int x[10090],y[10090];
 9 int f[10090][1090];
10 struct tube{
11     int p,l,h;
12 }tu[1090];
13 
14 bool cmp(tube a,tube b)
15 {
16     return a.p<b.p;
17 }
18 
19 int main()
20 {
21     scanf("%d%d%d",&n,&m,&k);
22     for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
23     for(int i=1;i<=k;i++)
24         scanf("%d%d%d",&tu[i].p,&tu[i].l,&tu[i].h);
25     sort(tu+1,tu+1+k,cmp);//输入顺序不定 
26     memset(f,127,sizeof(f));
27     for(int i=0;i<=m;i++) f[0][i]=0;
28     for(int i=1;i<=n;i++)
29     {
30         if(tu[pos].p==i)
31         {
32             for(int j=1;j<tu[pos].h;j++)
33                 if(j-x[i]>0)
34                     f[i][j]=min(f[i][j],min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1));
35             for(int j=1;j<tu[pos].h;j++)
36                 if(j+y[i]<=m&&j>tu[pos].l)
37                     f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
38             bool flag=0;
39             for(int j=1;j<tu[pos].h;j++)
40             {
41                 if(j<=tu[pos].l) f[i][j]=1e8;
42                 if(f[i][j]<1e7) flag=1;
43             }
44             if(!flag)
45             {
46                 printf("0\n%d",pos-1);
47                 return 0;
48             }
49             pos++;
50         }
51         else
52         {
53             for(int j=1;j<=m;j++)
54                 if(j-x[i]>0)
55                     f[i][j]=min(f[i][j],min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1));
56             for(int j=1;j<=m;j++)
57                 if(j+y[i]<=m)
58                     f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
59             for(int j=m-x[i];j<=m;j++)
60                 f[i][m]=min(f[i][m],min(f[i][j]+1,f[i-1][j]+1));
61         }
62     }
63     for(int i=1;i<=m;i++)
64         ans=min(ans,f[n][i]);
65     printf("1\n%d",ans);
66     return 0;
67 }
Pur code

小结:这题的细节比较多,那个优化方法好像也比较难想的样子,手动模拟是个不错的选择==