免费馅饼 HDU - 1176 【经典DP】

做过的题Σ( ° △ °|||)︴

#include <stdio.h>
#include <iostream>
#include <string.h>

using namespace std;
typedef long long ll;

const int N=1e5+3;
int dp[100005][20];

int main(void){
    int n;
    while(cin>>n){
        if(n==0)    return 0;
        memset(dp,0,sizeof(dp));
        int tmax=-1;
        for(int i=1;i<=n;i++){
            int x,t;
            scanf("%d%d",&x,&t);
            tmax=max(tmax,t);
            dp[t][x]++;
        }
        //cout <<"TMAX=" << tmax << endl;
        for(int i=tmax-1;i>=0;i--){
            for(int j=0;j<=11;j++){
                if(j==0)    dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
                else if(j==11)  dp[i][j]+=max(dp[i+1][j],dp[i+1][j-1]);
                else    dp[i][j]+=max(dp[i+1][j],max(dp[i+1][j-1],dp[i+1][j+1]));
            }
        }
        /*for(int i=0;i<=tmax;i++){
            for(int j=1;j<=11;j++){
                printf("%d ",dp[i][j]);
            }
            puts("");
        }*/
        cout << dp[0][5] << endl;
    }
    return 0;
}