首页 > 代码库 > bzoj1592[Usaco2008 Feb]Making the Grade 路面修整*
bzoj1592[Usaco2008 Feb]Making the Grade 路面修整*
bzoj1592[Usaco2008 Feb]Making the Grade 路面修整
题意：
某条路n段，每段高度hi，现在要将路修成不上升或不下降序列，问最小费用，把高度a修成b费用为|a-b|。n≤2000。
题解：
有个结论，每段路修成的高度必定是原序列中已经出现过的高度（因为修好的路是非严格单调）。所以直接离散化，然后dp（修成不下降）：f[i][j]=min(f[i-1][k]+abs(a[j]-a[k])),a[j]>=a[k]。但是这样会T，而a数组因为之前的离散化是单调的，所以可以用前缀最小值数组维护一下f[i-1][1]到f[i-1][n]的最小值，然后就可以递推了。
代码：
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 2010 7 #define ll long long 8 #define INF 10000000000000000 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 int n,tot,a[maxn],v[maxn]; ll f[maxn],ans,mn[maxn];18 struct nd{int v,id;}nds[maxn]; bool cmp(nd a,nd b){return a.v<b.v;}19 int main(){20 n=read(); inc(i,1,n)nds[i]=(nd){read(),i}; sort(nds+1,nds+n+1,cmp);21 inc(i,1,n){if(i==1||nds[i].v!=nds[i-1].v)v[++tot]=nds[i].v; a[nds[i].id]=tot;}22 memset(f,0,sizeof(f)); ans=INF;23 inc(i,1,n){24 mn[tot]=f[tot]+abs(v[tot]-v[a[i]]);25 for(int j=tot-1;j>=1;j--)mn[j]=min(mn[j+1],f[j]+abs(v[j]-v[a[i]])); inc(j,1,tot)f[j]=mn[j];26 }27 inc(i,1,tot)ans=min(ans,f[i]); memset(f,0,sizeof(f));28 inc(i,1,n){29 mn[1]=f[1]+abs(v[1]-v[a[i]]);30 inc(j,2,tot)mn[j]=min(mn[j-1],f[j]+abs(v[j]-v[a[i]])); inc(j,1,tot)f[j]=mn[j];31 }32 inc(i,1,tot)ans=min(ans,f[i]); printf("%lld",ans); return 0;33 }
20160921
bzoj1592[Usaco2008 Feb]Making the Grade 路面修整*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。