首页 > 代码库 > bzoj1649[Usaco2006 Dec]Cow Roller Coaster*
bzoj1649[Usaco2006 Dec]Cow Roller Coaster*
bzoj1649[Usaco2006 Dec]Cow Roller Coaster
题意：
n条钢轨，第i条起点pi，长度为wi，价钱ci，有趣度fi，要求从0修到l使得总价钱不超过b的前提下有趣度和最大。n≤10000，l≤1000，b≤1000。
题解：
首先把钢轨组织成链表。接着dp：f[i][j]表示修到第i处花钱j，则f[i][j]=f[i-wk][j-ck]+fk,k为终点为i的钢轨。边界则设为f[0][j]都为0，f[i][j]都为负无穷，以保证从0开始修。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 1010 7 #define ll long long 8 #define INF 0x3fffffff 9 using namespace std;10 11 inline int read(){12 char ch=getchar(); int f=1,x=0;13 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}14 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();15 return f*x;16 }17 struct nd{int w,f,c,n;}nds[maxn*10]; int g[maxn];18 int f[maxn][maxn],l,n,b;19 int main(){20 l=read(); n=read(); b=read();21 inc(i,1,n){22 int o=read(),p=read(),q=read(),r=read(); nds[i]=(nd){p,q,r,g[o+p]}; g[o+p]=i;23 }24 inc(i,1,l)inc(j,0,b)f[i][j]=-INF; inc(i,0,b)f[0][i]=0;25 inc(i,0,l){26 inc(j,0,b){27 for(int k=g[i];k;k=nds[k].n)28 if(j>=nds[k].c)f[i][j]=max(f[i][j],f[i-nds[k].w][j-nds[k].c]+nds[k].f);29 }30 }31 printf("%d",f[l][b]<0?-1:f[l][b]); return 0;32 }
20160923
bzoj1649[Usaco2006 Dec]Cow Roller Coaster*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。