xindoo is
always here

hdoj 1176免费馅饼(dp)


题目链接

//2013-05-17-21.08
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 100004;

int dp[maxn][12];

int main()
{
    int n, maxt, t, x;
    int tmax;
    while(scanf("%d", &n) && n)
    {
        memset(dp, 0, sizeof(dp));
        maxt = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%d%d",&x, &t);
            maxt = max(t, maxt);
            dp[t][x]++;
        }
        t = maxt;
        for (t--; t >= 0; t--)
        {
            for (int i = 0; i <= 10; i++)
            {
                if (i == 0)
                    tmax = max(dp[t+1][i], dp[t+1][i+1]);
                else if (i == 10)
                    tmax = max(dp[t+1][i], dp[t+1][i-1]);
                else
                {
                    tmax = max(dp[t+1][i-1], dp[t+1][i]);
                    tmax = max(tmax, dp[t+1][i+1]);
                }
                dp[t][i] += tmax;
            }
        }
        printf("%d\n", dp[0][5]);
    }
    return 0;
}
打赏
未经允许不得转载:XINDOO » hdoj 1176免费馅饼(dp)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏