首页 > 代码库 > hdu 1176 - 免费馅饼
hdu 1176 - 免费馅饼
题目:接馅饼,天上掉馅饼,活会落在0~10,11个位置上,单位时间可以移动到相邻的格子里;
问最大能接到多少。
分析:dp,离散化。
阶段:时间(离散化的);
状态:某时间站在当前点,能得到的最大值;
决策:按照时间计算前一位置可到达当前位置的区间来更新当前点;
说明:初始化 5位置0,其他的都 -10或者其他的就可以了。(2011-09-19 07:56)
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct ode { int S,T; }Node; Node N[ 100001 ]; int F[ 100001 ][ 11 ]; int cmp( const void* a, const void* b ) { return ((Node*)a)->T - ((Node*)b)->T; } int main() { int n; while ( scanf("%d",&n) && n ) { for ( int i = 1 ; i <= n ; ++ i ) scanf("%d%d",&N[ i ].S,&N[ i ].T); qsort( &N[ 1 ], n, sizeof( Node ), cmp ); for ( int i = 0 ; i <= 10 ; ++ i ) F[ 0 ][ i ] = -10; F[ 0 ][ 5 ] = 0; N[ 0 ].T = 0; for ( int i = 1 ; i <= n ; ++ i ) { for ( int j = 0 ; j <= 10 ; ++ j ) F[ i ][ j ] = F[ i-1 ][ j ]; for ( int j = 0 ; j <= 10 ; ++ j ) for ( int k = 0 ; k <= 10 ; ++ k ) if ( abs( j-k ) <= N[ i ].T - N[ i-1 ].T && F[ i ][ j ] < F[ i-1 ][ k ] ) F[ i ][ j ] = F[ i-1 ][ k ]; F[ i ][ N[ i ].S ] += 1; } int Max = 0; for ( int i = 0 ; i <= 10 ; ++ i ) if ( Max < F[ n ][ i ] ) Max = F[ n ][ i ]; printf("%d\n",Max); } return 0; }
hdu 1176 - 免费馅饼
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。