P2885 [USACO07NOV]电话线Telephone Wire
传送门
(题目描述有毒,这里的树不是指n点n−1条边的连通图,而是普普通通的树(植物))
考虑DP,很容易想到一个O(nC2)的DP,令dp[i][j]为第i棵树拔到j的高度,且1到i的所有树之间都连了线的最小花费,我们有:
dp[i][j]=min{dp[i−1][k]+c×∣j−k∣}+(j−h[i])2
实际操作过程中,假设一开始最高的树高度为maxh,我们发现把一棵树拔到maxh以上永远是亏本的,所以不用考虑。
代码,开了O2才能在洛谷上面AC:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #include <bits/stdc++.h> #define MAXN 100005 #define MAXM 105 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } int f[MAXN][MAXM]; int h[MAXN],maxh; int main(){ int n=read(),c=read(); maxh=-0x7fffffff; for (register int i=1;i<=n;++i){ h[i]=read(); maxh=max(maxh,h[i]); } for (register int i=h[1];i<=maxh;++i){ f[1][i]=(i-h[1])*(i-h[1]); } for (register int i=2;i<=n;++i){ for (register int j=h[i];j<=maxh;++j){ f[i][j]=0x7fffffff; for (register int k=h[i-1];k<=maxh;++k){ f[i][j]=min(f[i][j],f[i-1][k]+c*abs(j-k)); } f[i][j]+=(j-h[i])*(j-h[i]); } } int ans=0x7fffffff; for (register int i=h[n];i<=maxh;++i){ ans=min(ans,f[n][i]); } printf("%d\n",ans); }
|
考虑如何优化,发现c×abs(j−p)具有单调性,所以就可以O(nk)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include <bits/stdc++.h> #define MAXN 100005 #define MAXM 105 #define Calc(p) (f[i-1][p]+c*abs(j-(p))) using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } int f[MAXN][MAXM]; int h[MAXN],maxh; int main(){ int n=read(),c=read(); maxh=-0x7fffffff; for (register int i=1;i<=n;++i){ h[i]=read(); maxh=max(maxh,h[i]); } for (register int i=1;i<=n;++i){ int p=h[i-1]; for (register int j=h[i];j<=maxh;++j){ while (p<maxh&&Calc(p+1)<Calc(p)) p++; f[i][j]=Calc(p)+(j-h[i])*(j-h[i]); } } int ans=0x7fffffff; for (register int i=h[n];i<=maxh;++i){ ans=min(ans,f[n][i]); } printf("%d\n",ans); }
|