原题链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=613
AC代码:
#include<stdio.h> #include<stdlib.h> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int Max = 100000 +10; int dp[Max][12]; int MAX (int a ,int b ,int c) { return max(max(a,b),c); } void dp_find(int n) { int i,j; for(i = 1;i <= n;i ++ ) { for(j = 1;j <= 11;j ++) { int ans = MAX(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]); dp[i][j] += ans; } } } void display(int n) { int i,j; for(i = 1;i <= n;i ++ ) { for(j = 1;j <= 11;j ++) { printf("%d ",dp[i][j]); } printf("\n"); } } int main() { int i,j,k,n,x,y; int beg,end; while(scanf("%d",&n)&&n) { int ans = 0; j = 1; memset(dp,0,sizeof(dp)); k = 6; for(i = 0;i < n; i++) { scanf("%d%d",&x,&y); x++; if(x >= 12) continue; if(x >= k - y && x <= k + y) { dp[y][x] ++ ; j = max(j,y); } } dp_find(j); for(i = 1;i <= 11;i ++) ans = max(ans,dp[j][i]); printf("%d\n",ans); } }