HDU - 1176 免费馅饼（数塔类型DP）
题目链接：
大致题意:
在0到10的坐标上，会掉落n个馅饼，给出馅饼掉落的位置和时间，主人公一次只能接到他所在位置即左右三个位置上掉落的馅饼，求主人公最多可以接到多少馅饼（初始在5这个位置）
解题思路:
数她 逆着dp
AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 15, M = 1e5 + 10;
int n;
int w[N][M]; //在i的位置第j时间掉落的馅饼数
int f[N][M]; //在i的位置第j时间接到的最多馅饼数
int main() {
while (cin >> n, n) {
memset(w, 0, sizeof w);
memset(f, 0, sizeof f);
int x, t, maxt = 0;
for (int i = 0; i < n; ++i) {
scanf("%d%d", &x, &t);
//cin >> x >> t;
w[x][t]++;
maxt = max(maxt, t);
}
for (int i = 0; i < N; ++i)f[i][maxt] = w[i][maxt]; //初始化
for (int j = maxt - 1; j >= 0; --j)
for (int i = 0; i <= 10; ++i)
f[i][j] = max(f[i - 1][j + 1], max(f[i][j + 1], f[i + 1][j + 1])) + w[i][j];
cout << f[5][0] << endl;
}
return 0;
}
END
上一篇：
通过多线程提高代码的执行效率例子
下一篇：
Java多线程-交叉打印26个字母