题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1176
题意不解释了
简单的记忆化搜索可以拿来练练手,注意要从pos = 5 开始搜索
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const int M = 1e5 + 10;
int dp[15][M] , t2[M][12];
int dfs(int pos , int count) {
if(count == 0) {
if(pos == 6) {
return 0;
}
else {
return -1;
}
}
if(dp[pos][count] != -1)
return dp[pos][count];
int sum = 0;
if(pos == 1) {
sum += max(dfs(pos + 1 , count - 1) , dfs(pos , count - 1));
}
else if(pos == 11) {
sum += max(dfs(pos - 1 , count - 1) , dfs(pos , count - 1));
}
else {
sum += max(max(dfs(pos - 1 , count - 1) , dfs(pos + 1 , count - 1)) , dfs(pos , count - 1));
}
if(sum != -1) {
sum += t2[count][pos];
dp[pos][count] = sum;
}
return sum;
}
int main() {
int n;
while(scanf("%d" , &n) != EOF) {
if(n == 0)
break;
memset(t2 , 0 , sizeof(t2));
int T = 0;
for(int i = 0 ; i < n ; i++) {
int x , y;
scanf("%d%d" , &x , &y);
t2[y][x + 1]++;
T = max(T , y);
}
memset(dp , -1 , sizeof(dp));
int MAX = 0;
for(int i = 1 ; i <= 11 ; i++) {
MAX = max(MAX , dfs(i , T));
}
printf("%d\n" , MAX);
}
return 0;
}