题目链接
bzoj1205: [HNOI2005]星际贸易
题解
辣鸡题面，毁我青春 辣鸡题面，毁我青 辣鸡题面，毁我 辣鸡题面，毁 第一问，背包dp 第二问 问题转化为在一个序列上经过好多点走到终点， 符合各项条件的情况下费用最小，其中有某些点必须经过。 g[u][fu]表示将要离开点u而还没有离开的时候有fu个燃料。 得到g[u][fu]=min(g[u][fu-1]+p[u],g[v][fu+2]) 、 复杂度n^3 单调队列维护fu相同时g[fu][v]的最小值 n^2
代码
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-')f = - 1; c = getchar();}
while(c <= '9' && c >= '0')x = x * 10 + c - '0',c= getchar();
return x * f;
}
const int maxn = 2007;
int n,m,r,l0; //m max afford // r : 最大燃料量，//l0 不做维护飞的最大距离
int a[maxn],l[maxn],p[maxn],c[maxn],f[maxn][maxn * 2];
int g[maxn][maxn * 2];
bool ch[maxn][maxn];
int q[maxn ][maxn] ,h[maxn],t[maxn];
const int INF = 1e9;
bool must[maxn];
int solve() {
memset(g,0x3f,sizeof g);
memset(t,-1,sizeof t);
q[r][t[r] = 0] = g[0][r] = 0 ;
for(int u = 1;u <= n;++ u)
for(int fu = 0;fu <= r;++ fu) {
if(fu > 0 && p[u]) g[u][fu] = min(g[u][fu],g[u][fu- 1] + p[u]);
int k = fu + 2;
if(k <= r) {
while(h[k] <= t[k] && l[u] - l[q[k][h[k]]] > l0) h[k] ++;
if(h[k] <= t[k]) g[u][fu] = std::min(g[u][fu],g[q[k][h[k]]][k] + c[u]);
}
while(h[fu] <= t[fu] && g[u][fu] < g[q[fu][t[fu]]][fu]) t[fu] --;
if(must[u]) t[fu] = h[fu] - 1;
q[fu][++ t[fu]] = u;
}
int ret = INF;
for(int i = 0;i <= r;++ i) ret = std::min(ret,g[n][i]);
return ret;
}
void get(int i,int j) {
if(! i ) return ;
if(ch[i][j]) must[i] = true , get(i - 1,j - a[i]);
else get(i - 1,j) ;
}
int main() {
n = read(),m = read(),r = read(),l0 = read();
r = std::min(r,2 * n);
for(int b,i = 1;i <= n;++ i) {
a[i] = read(),b = read(),l[i] = read(),p[i] = read(),c[i] = read();
for(int j = m;j >= 0;-- j) {
f[i][j] = f[i - 1][j];
if(j >= a[i] && f[i - 1][j - a[i]] + b > f[i][j]) {
f[i][j] = f[i - 1][j - a[i]] + b;
ch[i][j] = 1;
}
}
}
get(n,m);
int ned = solve();
if(ned >= INF) puts("Poor Coke!");
else printf("%d %d\n",f[n][m],f[n][m] - ned);
return 0;
}
转载于:https://www.cnblogs.com/sssy/p/9398054.html
