荆门网站建设514885,wordpress可以做门户网站,为网站生成rss,虚拟主机做网站教程免费馅饼 Time Limit: 1000MS Memory Limit: 32768KBSubmit Statistic DiscussProblem Description 都说天上不会掉馅饼#xff0c;但有一天gameboy正走在回家的小径上#xff0c;忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了#xff0c;这馅饼别处都不掉但有一天gameboy正走在回家的小径上忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了这馅饼别处都不掉就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏虽然在游戏中是个身手敏捷的高手但在现实中运动神经特别迟钝每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标 为了使问题简化假设在接下来的一段时间里馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置因此在第一秒他只能接到4,5,6这三个位置中期中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼假设他的背包可以容纳无穷多个馅饼Input
输入数据有多组。每组数据的第一行为以正整数n(0 n 100000)表示有n个馅饼掉在这条小径上。在结下来的n行中每行有两个整数x,T(0 T 100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n0时输入结束。 Output
每一组输入数据对应一行输出。输出一个整数m表示gameboy最多可能接到m个馅饼。 提示本题的输入数据量比较大建议用scanf读入用cin可能会超时。Example Input 6
5 1
4 1
6 1
7 2
7 2
8 3
0 Example Output 4 一开始写的超时代码 /*
先按照时间顺序优先到后以及落得位置有小到大排好序然后再依次进行比较
*/
#includeiostream
#includecstdio
#includecmath
#includealgorithm
using namespace std;
struct st
{int p,t;
}a[100005],temp;
int cmp(st a,st b)
{return a.tb.t;
}
int main()
{int t,q0;while(scanf(%d,t),t){q0;for(int i0;it;i)scanf(%d%d,a[i].p,a[i].t);stable_sort(a,at,cmp);int l0,_max0,dp[100000]{0},k0;for(int i0;it-1;i){for(int ji1;jti!j;j){if((a[j].p-a[i].p)-1(a[j].p-a[i].p)1(a[j].t-a[i].t)-1(a[j].t-a[i].t)1){k1;dp[j]dp[i]1;}}}for(int i0;it;i)if(_maxdp[i])_maxdp[i];printf(%d\n,_maxk);}return 0;
}
后来用的是二维数组来写。设a[i][j]为第i秒的j位置掉下的馅饼数量f[i][j]为第i秒在j位置接馅饼最多可以接到的最多馅饼数量。由于每秒只能移动一个位置因此这一状态可能由三种情况达到
f[i - 1][j - 1]
f[i - 1][j]
f[i - 1][j 1]
这三种情况中的最大值加上当前位置可以接到的馅饼数即是当前位置可以接到的最大馅饼数量
f [ i ] [ j ] max ( f [ i - 1 ] [ j - 1 ] , f [ i - 1 ] [ j ] , f [ i - 1 ] [ j 1 ] ) a [ i ] [ j ] ;
可以看出当前状态与之前同一阶段的多个状态有关而类似于 Ugly Numbers 等动态规划中的每一阶段都只有一个状态为区分两者我将它称为 二维动态规划 。当然这道题只是二维动态规划中最简单的一种罢了。
#includestdio.h
#includecstring
#includecmath
#includealgorithm
using namespace std;
int dp[100005][12];
int main()
{int n,i,j,maxt;int x,t;while(scanf(%d,n),n){maxt0;memset(dp,0,sizeof(dp));for(i0;in;i){scanf(%d%d,x,t);dp[t][x];if(maxtt) maxtt;}for(imaxt-1;i0;i--){dp[i][0]max(dp[i1][1],dp[i1][0]);for(j1;j11;j){dp[i][j]max(max(dp[i1][j-1],dp[i1][j]),dp[i1][j1]);}}printf(%d\n,dp[0][5]);}return 0;
}
