（复习次数：1）HDJ 1176 免费馅饼 -- 动态规划

http://acm.hdu.edu.cn/showproblem.php?pid=1176
状态dp[t][x]表示i时刻在坐标j出最多能接到的馅饼数。
倒爬在动态规划里又常见又重要注意！！！
状态转移方程：

dp[t][x] = Max(dp[t+1][x+i],i为-1,0,1) + dp[t][x].
(也要注意dp[t][x]是可能重叠超过1的）
最后dp[0][5]即为所求结果。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define N 100003
using namespace std;
int dp[N][13];
int Max(int t,int x)
{
    if(x==0){
    return dp[t][x]>dp[t][x+1]?dp[t][x]:dp[t][x+1];}else{
    int max=0;for(int i=-1;i<=1;i++){
    if(max<dp[t][x+i]){
    max=dp[t][x+i];}}return max;}
}
int main()
{
    //FILE*fp=fopen("text.in","r");//------记得最后注释掉！！ int n;while(scanf("%d",&n),n)//while(fscanf(fp,"%d",&n),n){
    mem(dp,0);int x,t;for(int i=1;i<=n;i++){
    scanf("%d%d",&x,&t);//fscanf(fp,"%d%d",&x,&t);dp[t][x]+=1;}for(t=99998;t>=0;t--){
    for(x=0;x<=10;x++){
    dp[t][x]=Max(t+1,x)+dp[t][x];}}printf("%d\n",dp[0][5]);}return 0;
}

复习
5/18

#include<bits/stdc++.h>
#ifdef LOCAL
FILE*FP=freopen("text.in","r",stdin);
#endif
#define N 100005
#define _max(a,b,c) max(max((a),(b)),c)
using namespace std;
int a[N][11],s[N][11];
inline int get(int t,int x){
    if(x>10||x<0)return 0;return s[t][x];
}
int main(){
    int n;while(~scanf("%d",&n)){
    memset(a,0,sizeof(a));memset(s,0,sizeof(s));if(n==0)break;int x,t;for(int i=0;i<n;i++){
    scanf("%d%d",&x,&t);a[t][x]++;}for(int i=100000;i>=0;i--){
    for(int j=0;j<=10;j++){
    s[i][j]=_max(get(i+1,j-1),get(i+1,j),get(i+1,j+1))+a[i][j];}}printf("%d\n",s[0][5]);}return 0;
}