<span>codeforces713C Sonya and Problem Wihtout a Legend（dp）</span>
题意：
给你一个序列，你可以改变任意一个数字的大小，代价是改变量
问你使其变成严格单调递增序列的最小代价
思路：
单调不减的最小代价可以用O（n^2）的时间搞出来，而让单调递增转化为单调不减只需要让a[i]-i就可以了
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <string> #include <cmath> #include <stdlib.h> #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define mkp make_pair template<class T>inline void rd(T &x) { char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int inf=0x3f3f3f3f; const int N=3e3+10; int a[N],b[N],n; LL dp[N][N]; int main() { #ifndef ONLINE_JUDGE //IN #endif rd(n); rep(i,1,n) { rd(a[i]); a[i]-=i; b[i]=a[i]; } sort(b+1,b+n+1); int bn=unique(b+1,b+n+1)-b-1; memset(dp,inf,sizeof(dp)); rep(i,1,n) rep(j,1,bn) dp[i][j]=(i>1)?min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j])):min(dp[i][j-1],1ll*abs(a[i]-b[j])); printf("%I64d\n",dp[n][bn]); return 0; }
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <string> #include <cmath> #include <stdlib.h> #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define mkp make_pair template<class T>inline void rd(T &x) { char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int inf=0x3f3f3f3f; const int N=3e3+10; int a[N],b[N],n; LL dp[N][N]; int main() { #ifndef ONLINE_JUDGE //IN #endif rd(n); rep(i,1,n) { rd(a[i]); a[i]-=i; b[i]=a[i]; } sort(b+1,b+n+1); rep(i,1,n) { LL mi=dp[i-1][1]; rep(j,1,n) { mi=min(mi,dp[i-1][j]); dp[i][j]=abs(a[i]-b[j])+mi; } } rep(i,2,n) dp[n][1]=min(dp[n][1],dp[n][i]); printf("%I64d\n",dp[n][1]); return 0; }
Momenta公司福利 293人发布
投递字节跳动等公司10个岗位 >
