3729 飞扬的小鸟
题目描述 Description
输入描述 Input Description
输出描述 Output Description
输出文件名为 bird.out。
共两行。
第一行，包含一个整数，如果可以成功完成游戏，则输出 1，否则输出 0。
第二行，包含一个整数，如果第一行为 1，则输出成功完成游戏需要最少点击屏幕数，
否则，输出小鸟最多可以通过多少个管道缝隙。
样例输入 Sample Input
【输入输出样例说明】
如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。
数据范围及提示 Data Size & Hint
对于 30%的数据：5≤n≤10，5≤m≤10，k=0，保证存在一组最优解使得同一单位时间最多点击屏幕 3 次；
对于 50%的数据：5≤n≤20，5≤m≤10，保证存在一组最优解使得同一单位时间最多点击屏幕 3 次；
对于 70%的数据：5≤n≤1000，5≤m≤100；
对于 100%的数据： 5≤n≤10000， 5≤m≤1000， 0≤k<n， 0<X<m， 0<Y<m， 0<P<n， 0≤L<H ≤m，L +1<H。
思路:
首先想到设分f[i][j]表示到达地i行第j列所需要的最少点击屏幕次数。转移方程为
f[ i ][ j ]=min{f[ i-1 ][ j - k*x[i-1] ] + k} (1<= k <= j/x) 上升—— ①
f[ i ][ j ]=min{f[ i-1 ][ j + y[i-1] } ( j + y[i-1] <= m) 下降
显然，下降可以O(1)转移，主要问题在上升的转移。
我们将上升的方程变一下：
f[ i ][ j - x[i-1] ]=min{f[ i-1 ][ (j - x[i-1]) - (k-1)*x[i-1] ] + k -1} ——②
这是 f[ i ][ j - x[i-1] ] 的转移。
由 ② 化简可得：
f[ i ][ j - x[i-1] ]=min{f[ i-1 ][ j - k*x[ i-1] ] + k -1}
消去f[ i-1 ][ j - k*x[ i-1] ]
f[ i ][ j ]= f[ i ][ j - x[ i-1 ] ]+1
于是就可以O(n*m)的时间内出解啦~
@大佬%%%
代码:
#include <iostream> #include <cstdio> #include <cmath> #define INF 2100000000 #define LL long long using namespace std; const int Maxn = 10010; const int Maxm = 1010; int n,m,k; int x[Maxn],y[Maxn]; ///到达i行j列所需要的最少点击屏幕的次数 int dp[Maxn][Maxm]; struct bird { int u,d; }b[Maxn]; int main() { scanf("%d%d%d",&n,&m,&k); for(int i=0; i<n; ++i) scanf("%d%d",&x[i],&y[i]); ///初始化各坐标(若不被更新,则说明该横坐标上并不是管道) for(int i=1; i<=n; ++i) b[i].d=0,b[i].u=m+1; for(int i=0,p; i<k; ++i) { scanf("%d",&p); scanf("%d%d",&b[p].d,&b[p].u); } for(int i=1; i<=n; ++i) for(int j=0; j<=m; ++j) dp[i][j]=INF;///因为要取min,所以需要赋个极大值 ///因为j!=0,所以dp[0][0]=INF; dp[0][0]=INF; for(int i=1; i<=n; ++i) { ///暂时先不考虑管道的情况,进行更新dp数组 for(int j=x[i-1]; j<=m; ++j) { ///普通的转移(由上一个(i-1)刚好能跳的f[i-1].x的坐标处的值+1进行转移过来) dp[i][j]=min(dp[i][j],dp[i-1][j-x[i-1]]+1); ///见公式推出 dp[i][j]=min(dp[i][j],dp[i][j-x[i-1]]+1); ///因为不能够超过m,会出现比较多种的转移方程 if(j==m) for(int o=m-x[i-1]; o<=m; ++o) { ///位于i-1处,并且一跳能够够到m(j)的,用来进行i,j的更新 dp[i][j]=min(dp[i][j],dp[i-1][o]+1); ///见公式推出 dp[i][j]=min(dp[i][j],dp[i][o]+1); } } ///处理下落的情况,必须是合法的 for(int j=b[i].d+1; j<b[i].u; ++j) ///若合法 if(j+y[i-1]<=m) dp[i][j]=min(dp[i][j],dp[i-1][j+y[i-1]]); ///考虑当前管道缝隙的下界以下的地方是没有dp值的,所以重新将其赋值为最大值 for(int j=1; j<=b[i].d; ++j) dp[i][j]=INF; ///上界以上的地方也是没有dp值的 for(int j=m; j>=b[i].u; --j) dp[i][j]=INF; } int cnt=k,ans=INF; ///需要逆序枚举 for(int i=n; i>=1; --i) { for(int j=1; j<=m; ++j) ans=min(ans,dp[i][j]); ///如果ans(i)逆序被更新了,那么他一定就是最优解 ///因为胜利的结束条件是飞得远一直到横坐标为n if(ans!=INF) break; ///如果是管道 if(b[i].u<=m) cnt--; } ///在最后一个水管出现之前被break;那么被更新的ans即为最优解 if(cnt==k) printf("1 %d ",ans); ///据题目要求输出最多能通过几个管道 else printf("0 %d ",cnt); return 0; }