http://poj.org/problem?id=3666
算法竞赛进阶指南一眼看过去全是不会做的题。。。
这题要用数学归纳法证明B的最优构造方案一定包含一种只用A中出现过的数字的情况，但我觉得我肯定想不到
然后就比较简单了，考虑B不下降的情况，f[i][j]表示前i个用A中的前j个数字，第i个恰好用第j这个数字的最小值
那么f[i][j]=min(f[i-1][k]+abs(a[i]-num[j])),(1<=k<=j) ，这个min就可以边走边维护了
B不上升的情况直接把原A数组反过来再跑一遍就行
#include<cstdio> #include<cstring> #include<algorithm> #define maxl 2010 using namespace std; int n,m; int a[maxl],num[maxl],b[maxl]; long long ans; long long f[maxl][maxl]; inline void prework() { for(int i=1;i<=n;i++) scanf("%d",&a[i]),num[i]=a[i]; sort(num+1,num+1+n); m=unique(num+1,num+1+n)-num-1; } inline void solv() { memset(f,0x3f,sizeof(f)); f[0][1]=0; long long tmp; for(int i=1;i<=n;i++) { tmp=f[0][0]; for(int j=1;j<=m;j++) { tmp=min(f[i-1][j],tmp); f[i][j]=tmp+abs(b[i]-num[j]); } } for(int j=1;j<=m;j++) ans=min(ans,f[n][j]); } inline void mainwork() { ans=1ll<<60; for(int i=1;i<=n;i++) b[i]=a[i]; solv(); for(int i=1;i<=n;i++) b[i]=a[n-i+1]; solv(); } inline void print() { printf("%lld\n",ans); } int main() { while(~scanf("%d",&n)) { prework(); mainwork(); print(); } return 0; }
