P2893 [USACO08FEB]修路
发布时间：2020-12-14 05:08:20 所属栏目：大数据 来源：网络整理
导读：直入主题。 农夫约翰想改造一条路，原来的路的每一段海拔是Ai，修理后是Bi花费|A_i–B_i|。我们要求修好的路是单调不升或者单调不降的。求最小花费。 数据范围：n=2000,0≤ Ai ≤ 1,000,000 (说真的，时隔几个月，发现这题其实挺简单的) 最一开始，就打了一
|
直入主题。 农夫约翰想改造一条路，原来的路的每一段海拔是Ai，修理后是Bi花费|A_i–B_i|。我们要求修好的路是单调不升或者单调不降的。求最小花费。 数据范围：n<=2000,0≤ Ai ≤ 1,000,000 (说真的，时隔几个月，发现这题其实挺简单的) 最一开始，就打了一个贪心。 #include<bits/stdc++.h>//本人打题目时很喜欢万能头 using namespace std; const int maxn=2010; long long n,ans1,ans2; long long a[maxn]; int main() { scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(int i=1;i<n;i++) { if(a[i]>a[i+1]) ans1+=abs(a[i]-a[i+1]); //printf("%dn",ans1); } for(int i=n;i>1;i--) { if(a[i]>a[i-1]) ans2+=abs(a[i-1]-a[i]); //printf("%dn",ans2); } printf("%d",min(ans1,ans2)); return 0; }
? 此贪心思路 很容易发现，如果想要最小值的话，凹下去的土块一定会被填起来，而且填的高度一定会使这个土块和两侧最低的那个相平（比如样例第三个土块，填起来一定会和 二 一样高）于是考虑跑两遍，一个单增，一个单减。 结果：40分 。。。 随手一组hack数据： 9 5 5 5 1 1 1 5 5 5； 我没有及时更新高度，以至于会有后效性。 于是我每次减完会把它更新一次高度。 但是发现，还是会有后效性，hack数据还是毒瘤。 我终于想到了dp 接下来考虑转移方程式 考虑第i个土块，对其有影响的数据只有前i个土块的高度，还有本土块的高度，所以： 我们用dp[i][j]将前i段变作不下降序列，且第j段道路的高度为j时的最小花费
? 但是，j的枚举会把时间炸上天！！！！ 通过前面的结论，我们发现，最小的填补一定会在目标高度中出现，所以我们开另外一个数组，把高度存到里面，排序，从里面找一个合适的Ai，就省去了遍历1—100000000的时间 继续方程式。写出来就是这样，前i个柱子最小（此为单调不递减） 此题，洛谷数据过于划水以至于只考虑单增就可以过了。 于是放代码（只放单增的了） #include<bits/stdc++.h>
using namespace std; const int inf=0x7fffffff; const int maxn=2010; int n; int a[maxn],b[maxn]; int dp[maxn][maxn]; int main() { int ans=inf; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(j==1)//因为循环边界，所以当j==1我们要特判一发，把1拍到最低
dp[i][j]=dp[i-1][j]+abs(a[i]-b[j]); else dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(a[i] - b[j]));//拍土了
if(i==n) ans=min(dp[i][j],ans); } } printf("%dn",ans); return 0; }
?（膜拜一下隔壁dp神仙） （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
