简单DP
dp[i][j] 表示 i 时间 在 J 位置上有多少个馅饼
时间从0开始 ,
每一秒都有三种状态 dp[i+1][j] dp[i+1][j-1] dp[i+1][j+1]
j 从0开始但是J- 1的话就会为负数 所以全部+1
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int const MAXN = 100010; int dp[MAXN][20],a[MAXN][20]; inline int Max(int a,int b){ return a>b?a:b; } inline int Abs(int a,int b){ return a>0?a:-a; } int main(){ int n; while(~scanf("%d",&n),n){ memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); for(int i = 1;i <= n;i++){ int x,t; scanf("%d%d",&x,&t); a[t][x + 1]++; } for(int i = 100000;i >= 0;i--){ for(int j = 1;j <= 11;j++){ int v = a[i][j]; dp[i][j] = Max(dp[i + 1][j],Max(dp[i + 1][j - 1],dp[i + 1][j + 1])) + v; } } printf("%d\n",dp[0][6]); } return 0; }