>免费馅饼
题目 传送门
>题意&分析： 题目很好理解，注意初始 t=0 时刻的位置处于 x=5 。可以构建一个矩阵，行代表时间 t，列代表在馅饼落下的位置 x ，所以 dp[ i ][ j ] 记录的是 t=i 时刻在 x=j 位置落下的馅饼数量。
>代码如下：
#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define TEST cout<<"stop here"<<endl using namespace std; typedef long long ll; const ll mod = 1e9 + 7; int dp[100010][15]; int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); int n; while(cin>>n && n){ memset(dp,0,sizeof(dp)); int maxt = 0; for(int i=0;i<n;i++){ int x,t; cin>>x>>t; dp[t][x]++; if(maxt < t) maxt = t; } for(int i=maxt-1;i>=0;i--){//(0,5)是初始位置 for(int j=0;j<=10;j++){ if(j == 0) dp[i][j] += max(dp[i+1][j],dp[i+1][j+1]); else if(j == 10) dp[i][j] += max(dp[i+1][j],dp[i+1][j-1]); else dp[i][j] += max(max(dp[i+1][j],dp[i+1][j+1]),dp[i+1][j-1]); } } cout<< dp[0][5] <<endl;//答案是初始时候的位置 } return 0; }