首页 > 代码库 > 把一个序列转换成严格递增序列的最小花费 CF E - Sonya and Problem Wihtout a Legend
把一个序列转换成严格递增序列的最小花费 CF E - Sonya and Problem Wihtout a Legend
1 //把一个序列转换成严格递增序列的最小花费 CF E - Sonya and Problem Wihtout a Legend 2 //dp[i][j]:把第i个数转成第j小的数,最小花费 3 //此题与poj 3666相似 a[i]转换成a[i]-i 4 5 #include <iostream> 6 #include <cstdio> 7 #include <cstdlib> 8 #include <algorithm> 9 #include <vector>10 #include <math.h>11 #include <memory.h>12 using namespace std;13 #define LL long long14 typedef pair<int,int> pii;15 const int inf = 0x3f3f3f3f;16 const LL MOD =100000000LL;17 const int N = 3000+10;18 const double eps = 1e-8;19 void fre() {freopen("in.txt","r",stdin);}20 void freout() {freopen("out.txt","w",stdout);}21 inline int read() {int x=0,f=1;char ch=getchar();while(ch>‘9‘||ch<‘0‘) {if(ch==‘-‘) f=-1; ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}return x*f;}22 23 int a[N],b[N];24 LL dp[N][N];25 int main(){26 int n;27 scanf("%d",&n);28 for(int i=1;i<=n;i++){29 scanf("%d",&a[i]);30 a[i]-=i;31 b[i]=a[i];32 }33 sort(b+1,b+1+n);34 for(int i=1;i<=n;i++){35 dp[1][i]=abs(a[1]-b[i]);36 }37 for(int i=2;i<=n;i++){38 LL minn=1e18;39 for(int j=1;j<=n;j++){40 minn=min(minn,dp[i-1][j]);41 dp[i][j]=minn+abs(a[i]-b[j]);42 }43 }44 LL ans=1e18;45 for(int i=1;i<=n;i++){46 ans=min(ans,dp[n][i]);47 }48 cout<<ans<<endl;49 return 0;50 }
把一个序列转换成严格递增序列的最小花费 CF E - Sonya and Problem Wihtout a Legend
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。