HU-176-タピオカ

4498 ワード
データ構造

Crawling in process…
Crawling failed
Time Limit:1000 MS     メモリLimit:32768 KB     64 bit IO Format:%I 64 d&%I 64 u
Submit
Status
Practice
HDU 1176
Appint description:prayerhgq(2015-07-28)System Crawler(2015-11-14)
Description
天からパイが落ちないと言われていますが、ある日ガメボーイが家に帰る途中に、突然大きなパイが落ちてきました.というか、ガメボーイの人柄がとてもいいです.このパイは他のところには落ちないです.彼の隣の10メートルの範囲に落ちています.パイが床に落ちたらもちろん食べられません.だから、gameboyはすぐにリュックサックを外して迎えに行きます.しかし、小道の両側に人が立ってはいけないので、彼は小道でしか接できません.ゲームボーイはいつも部屋でゲームをしていますから、ゲームの中では素早いのが上手ですが、運動神経が非常に鈍いです.毎秒移動して1メートルを超えない範囲で墜落したパイをキャッチします.アイコン上の座標のようにこの小道をあげます.
問題を簡略化するために、次の時間にパイが0-10という11の位置に落ちていると仮定します.最初は5の位置に立っていましたので、第一秒は4、5、6の三つの位置の中の一つのパイしかもらえませんでした.gameboyはパイを一番多くもらうかもしれませんか?(彼のリュックサックが無限のパイを入れると仮定して)
 
Input
入力データは複数グループあります.各データの第一行為は正の整数n(0＜n＞100000)で、n個のパイがこの小道に落ちていることを表しています.結びのn行には、1行に2つの整数xがあり、T(0＜T＜100000)は、T番目の秒に1つのパイがx点に落ちていることを示しています.同じ秒で同じ点に複数のパイが落ちます.n=0で入力が終了します.
 
Output
入力データのセットは1ラインの出力に対応します.整数mを出力します.最大でmパイを受ける可能性があるという意味です.
ヒント:本題の入力データ量が大きいので、scanfで読み込むとcinでタイムアウトするかもしれません.
 
Sample Input

      
      
      
      

       
       
       
       6
5 1
4 1
6 1
7 2
7 2
8 3
0
               
Sample Output
4 




  ：             ，             ，               ，        ，       ，           。


   ：
 0                 5                         



 1               4 5 6


 2             3 4 5 6 7


 3           2 3 4 5 6 7 8


 4         1 2 3 4 5 6 7 8 9


 5       0 1 2 3 4 5 6 7 8 9 10


 6       0 1 2 3 4 5 6 7 8 9 10


 7  .................  


      5         0 1 2 3 4 5 6 7 8 9 10 ，   5           ，   5   ，       
0 10     ，    ，              ，   。
    ：
1：   ，      ，       。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
#define size 100050
using namespace std;
int dp[size][12];
int Max(int L, int m, int r)//          3      
{
	return max(max(L, m), r);
}
int main()
{
#ifdef OFFLINE
	freopen("t.txt", "r", stdin);
#endif
	int i, j, r, n, x, t;
	while(~scanf("%d", &n)&&n != 0){
		memset(dp, 0, sizeof(dp));
		r=0;
		while(n--){
			scanf("%d %d", &x, &t);
			dp[t][x]++;//   t       x
			r=max(r, t);//     
		}
		for(i=r-1;i>=0;i--){
			for(j=0;j<=10;j++){//              0，     。
				dp[i][j]+=Max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]);
			}
		}
		printf("%d
", dp[0][5]);
	}
	return 0;
}
2：        5   ，    ，      ！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
#define size 100050
using namespace std;
int dp[size][12];
int Max(int L, int m, int r)//          3      
{
	return max(max(L, m), r);
}
int main()
{
#ifdef OFFLINE
	freopen("t.txt", "r", stdin);
#endif
	int i, j, r, n, x, t;
	while(~scanf("%d", &n)&&n != 0){
		memset(dp, 0, sizeof(dp));
		r=0;
		while(n--){
			scanf("%d %d", &x, &t);
			dp[t][x]++;//   t       x
			r=max(r, t);//     
		}
		if(r>5){
			for(i=r-1;i>=5;i--){
				for(j=1;j<10;j++){
					dp[i][j]+=Max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]);
				}
				dp[i][0]+=max(dp[i+1][0], dp[i+1][1]);      0 10
				dp[i][10]+=max(dp[i+1][9], dp[i+1][10]);
			}
		}
		if(r>5) r=5;//      5 ,    4      ,   r-1,     r 5
		for(i=r-1;i>=0;i--){//  r<=5   
			for(j=5-i;j<=5+i;j++)//  i       (5-i), (2*i+1)  .
				dp[i][j]+=Max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]);
		}
		printf("%d
", dp[0][5]);
	}
	return 0;
}
zoj 3261 Connection in Galaxy War