HDU 1117 免费馅饼二维动态规划

60 阅读 0 评论 40 点赞

我是靠谱客的博主寒冷酒窝，最近开发中收集的这篇文章主要介绍HDU 1117 免费馅饼二维动态规划，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路：a[i][j]表示j秒在i位置的数目，dp[i][j]表示j秒在i位置最大可以收到的数目。

转移方程：d[i][j]=max(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1]);

 1 #include<iostream>
 2 #include<string>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 #include<cstdio>
 6 #include<set>
 7 #include<map>
 8 #include<vector>
 9 #include<cstring>
10 #include<stack>
11 #include<cmath>
12 #include<queue>
13 #include <bits/stdc++.h>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define ll long long
17 #define clc(a,b) memset(a,b,sizeof(a))
18 const int maxn=100010;
19 int a[maxn][11];
20 int dp[maxn][11];
21 int n;
22 int main()
23 {
24
while(~scanf("%d",&n),n)
25 
{
26
int x,y;
27
int time=0;
28
int maxx=0;
29
clc(a,0);
30
clc(dp,0);
31
for(int i=0;i<n;i++)
32 
{
33
scanf("%d%d",&x,&y);
34
a[y][x]++;
35
time=max(time,y);
36 
}
37
dp[1][4]=a[1][4];
38
dp[1][5]=a[1][5];
39
dp[1][6]=a[1][6];
40
for(int i=2;i<=time;i++)
41 
{
42
for(int j=0;j<11;j++)
43 
{
44
dp[i][j]=dp[i-1][j];
45
if(j>0)
46
dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
47
if(j<10)
48
dp[i][j]=max(dp[i][j],dp[i-1][j+1]);
49
dp[i][j]+=a[i][j];
50 
}
51 
}
52
for(int i=0;i<11;i++)
53 
{
54
if(maxx<dp[time][i])
55
maxx=dp[time][i];
56 
}
57
printf("%dn",maxx);
58 
}
59 }