nyoj613 免费馅饼 动态规划

//就想象成t行11列的数，从下往上遍历相加，找最大值。#include <stdio.h>
#include <string.h>
int dp[100005][13];
int Max(int a,int b,int c)
{
int max=a;
if(max<b)
max=b;
if(max<c)
max=c;
return max;
}
int main()
{
int n,x,t,max;
while(scanf("%d",&n)!=EOF&&n)
{
memset(dp,0,sizeof(dp));//初始化
max=0;
for(int i=0;i<n;i++)
{
scanf("%d %d",&x,&t);
dp[t][x+1]++;//x+1是为了下面的<span style="font-family: Arial, Helvetica, sans-serif;">Max(dp[i+1][j],dp[i+1][j+1],dp[i+1][j-1]),避免i-1为-1.</span>
if(t>max)
max=t;//找到最大时间
}
for(int i=max-1;i>=0;i--)//从最大时间-1开始
for(int j=1;j<=11;j++)
{
dp[i][j]=dp[i][j]+Max(dp[i+1][j],dp[i+1][j+1],dp[i+1][j-1]);
}
printf("%d\n",dp[0][6]);//因为最初dp[0][5+1].
}
return 0;
}