题解 | #免费馅饼#
免费馅饼
https://ac.nowcoder.com/acm/problem/16850
注意:本题为NOIP1998免费馅饼的简化版,缩小了w,h的范围,因此使用二维线性dp即可
本题考虑对于时间从后往前进行dp,若从前往后dp将十分复杂.
#include <iostream>
#include <vector>
using namespace std;
int dp[150][1300];
int ret[150][1300];
int dx[5] = {-2, -1, 0, 1, 2};
int main() {
int w, h;
cin >> w >> h;
int a, b, c, d, id = 0, mmax = 0;
while (cin >> a >> b >> c >> d) {
if ((h - 1) % c) continue;
int t = a + (h - 1) / c;
mmax = max(mmax, t);
dp[b][t] += d;
}
for (int i = mmax - 1; i >= 0; i --) { //dp[j][i], j代表位置, i代表时间.
for (int j = 1; j <= w; j ++) {
int t = 0, op = 0;
for (int k = 0; k < 5; k ++) {
int pos = j + dx[k];
if (pos > w || pos < 1) continue;
if (dp[pos][i + 1] > t) t = dp[pos][i + 1], op = dx[k];
}
ret[j][i] = op, dp[j][i] += t;
}
}
//cout << mmax << endl;
int ans = dp[w / 2 + 1][0];
cout << ans << endl;
vector <int> re;
int t = 0, pos = w / 2 + 1;
while (dp[pos][t] > 0) {
int dx = ret[pos][t];
re.push_back(dx);
pos += dx, t ++;
//cout << t << ' ' << dp[pos][t] << endl;
}
if(re.size())
for(int i = 0; i < re.size() - 1; i++) cout << re[i] << endl;
return 0;
}
三环集团开奖92人在聊
