[codevs3729]飞扬的小鸟
试题描述
输入
输出
输出文件名为 bird.out。
共两行。
第一行，包含一个整数，如果可以成功完成游戏，则输出 1，否则输出 0。
第二行，包含一个整数，如果第一行为 1，则输出成功完成游戏需要最少点击屏幕数，
否则，输出小鸟最多可以通过多少个管道缝隙。
输入输出示例
数据规模及约定
对于 30%的数据：5≤n≤10，5≤m≤10，k=0，保证存在一组最优解使得同一单位时间最多点击屏幕 3 次；
对于 50%的数据：5≤n≤20，5≤m≤10，保证存在一组最优解使得同一单位时间最多点击屏幕 3 次；
对于 70%的数据：5≤n≤1000，5≤m≤100；
对于 100%的数据： 5≤n≤10000， 5≤m≤1000， 0≤k<n， 0<X<m， 0<Y<m， 0<P<n， 0≤L<H ≤m，L +1<H。
题解
设 f[i][j] 表示横坐标在 i，纵坐标在 j 的最小点击次数（若不能达到这个点则为正无穷）。考虑每次转移，从 i-1 到 i，点击 k 次，纵坐标增加 X[i-1] * k（增加后不能超过 m）；或者不点击，纵坐标减小 Y[i-1]。
然而这样的转移是 O(n / X[i]) 的，当 X[i] 比较小时就过不了了，于是我们可以对 f[i][j] 的 j，及纵坐标进行模 X[i-1] 分类，然后维护一下前缀最小值即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); }
return x * f;
}
#define maxn 1010
#define maxl 10010
#define oo 2147483647
int n, m, k, f[2][maxn], minf[maxn], X[maxl], Y[maxl];
struct Tun {
int up, low, x;
Tun() {}
Tun(int _1, int _2, int _3): up(_1), low(_2), x(_3) {}
bool operator < (const Tun& t) const { return x < t.x; }
} ts[maxl];
int main() {
n = read(); m = read(); k = read();
for(int i = 0; i < n; i++) X[i] = read(), Y[i] = read();
for(int i = 1; i <= k; i++) {
int p = read(), l = read(), h = read();
ts[i] = Tun(h, l, p);
}
sort(ts + 1, ts + k + 1);
f[0][0] = oo;
for(int i = 1; i <= m; i++) f[0][i] = 0;
int cur = 1, kt = 1, at;
for(int i = 1; i <= n; i++, cur ^= 1) {
for(int j = 0; j <= m; j++) minf[j] = f[cur][j] = oo;
for(int j = 1; j <= m; j++)
if(j >= X[i-1]) {
int lf = f[cur^1][j-X[i-1]], mf = minf[j%X[i-1]];
minf[j%X[i-1]] = min(mf == oo ? oo : mf + 1, lf == oo ? oo : lf + 1);
f[cur][j] = min(f[cur][j], minf[j%X[i-1]]);
}
for(int j = m + 1; j <= m + X[i-1]; j++) {
int lf = f[cur^1][j-X[i-1]], mf = minf[j%X[i-1]];
minf[j%X[i-1]] = min(mf == oo ? oo : mf + 1, lf == oo ? oo : lf + 1);
f[cur][m] = min(f[cur][m], minf[j%X[i-1]]);
}
for(int j = 1; j <= m - Y[i-1]; j++)
f[cur][j] = min(f[cur][j], f[cur^1][j+Y[i-1]]);
if(kt <= k && ts[kt].x == i) {
// puts("here");
for(int j = 1; j <= ts[kt].low; j++) f[cur][j] = oo;
for(int j = ts[kt].up; j <= m; j++) f[cur][j] = oo;
kt++;
}
// for(int j = 1; j <= m; j++) printf("%d ", f[cur][j] < oo ? f[cur][j] : -1); putchar(‘\n‘);
for(int j = 1; j <= m; j++) if(f[cur][j] < oo) {
at = kt - 1; break;
}
}
int ans = oo;
for(int i = 1; i <= m; i++) ans = min(ans, f[cur^1][i]);
if(ans < oo) printf("1\n%d\n", ans);
else printf("0\n%d\n", at);
return 0;
}
原文：http://www.cnblogs.com/xiao-ju-ruo-xjr/p/5988414.html