wordpress贴内幻灯片,杭州seo按天计费,网站哪家公司做的最好,效果好的东莞品牌网站建设Problem Description
都说天上不会掉馅饼#xff0c;但有一天gameboy正走在回家的小径上#xff0c;忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了#xff0c;这馅饼别处都不掉#xff0c;就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了但有一天gameboy正走在回家的小径上忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了这馅饼别处都不掉就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏虽然在游戏中是个身手敏捷的高手但在现实中运动神经特别迟钝每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标 为了使问题简化假设在接下来的一段时间里馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置因此在第一秒他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼假设他的背包可以容纳无穷多个馅饼 Input
输入数据有多组。每组数据的第一行为以正整数n(0n100000)表示有n个馅饼掉在这条小径上。在结下来的n行中每行有两个整数x,T(0T100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n0时输入结束。 Output
每一组输入数据对应一行输出。输出一个整数m表示gameboy最多可能接到m个馅饼。 提示本题的输入数据量比较大建议用scanf读入用cin可能会超时。 Sample Input 6 5 1 4 1 6 1 7 2 7 2 8 3 0 Sample Output 4
问题分析用一个数组dp[t][x]表示在T秒X位置有一个饼落下即用一个矩阵记录饼的位置然后从底开始探索到最后最后一秒
找出饼最多的路线。
自己的代码还未通过
#includeiostream
#includealgorithm
using namespace std;
int dp[100001][12] {0};
int maxn(int x, int y, int j)
{int q;q (x y ? x j? x : j : y j ? y : j);return q;
}
int main()
{int n, x, t;while (scanf(%d, n) ! EOF n){int m 0;memset(dp, 0, sizeof(dp));for (int i 0; i n; i){scanf(%d %d, x, t);dp[t][x];if (t m)m t;}for (int i m - 1; i 0; i--){for (int j 0; j 10; j){dp[i][j] maxn(dp[i 1][j 1], dp[i 1][j], dp[i 1][j - 1]);}}printf(%d\n, dp[0][5]);}
}
AC代码 #includestdio.h#includestring.h#includeiostream#includealgorithm using namespace std;int dp[100001][12];//一开始数组开到11 WA了好几遍int maxn(int a,int b,int c){int max1;max1ab?a:b;max1max1c?max1:c;return max1;}int main(){int n,x,t;while(scanf(%d,n)!EOFn){int i,j,m0;memset(dp,0,sizeof(dp));for(i0;in;i){scanf(%d%d,x,t);dp[t][x];if(tm)mt;}for(im-1;i0;i--){//dp[i][0] max(dp[i1][0],dp[i1][1]); for(j0;j10;j)dp[i][j]maxn(dp[i1][j1],dp[i1][j],dp[i1][j-1]);//从三个方向寻找最大权值的方向} printf(%d\n,dp[0][5]);}return 0;}
