大意: 给定序列, 每次操作可以任选一个数+1/-1, 求最少操作数使序列严格递增.
序列全-i后转化为求最少操作数使序列非降, 那么贪心可以知道最后$a_i$一定是修改为某一个$a_j$了, 暴力dp即可.
#include#include #define REP(i,a,n) for(int i=a;i<=n;++i)using namespace std;typedef long long ll;const int N = 3e3+10;int n, a[N], b[N];ll dp[N][N];int main() { scanf("%d", &n); REP(i,1,n) scanf("%d", a+i),a[i]-=i,b[i]=a[i]; sort(b+1,b+1+n); REP(i,1,n) dp[i][0]=1e18; REP(i,1,n) REP(j,1,n) dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j])); printf("%lld\n", dp[n][n]);}