AtCoder AGC032D Rotation Sort (DP)

题目链接

https://atcoder.jp/contests/agc032/tasks/agc032_d

题解

又是一道神仙题啊啊啊啊。。。atcoder题真的做不来啊QAQ

第一步又是神仙转化: 对于把第一个挪到最后其他左移这件事情，可以转化为把第一个挪到最后和最后的下一个之间的某个位置(非整数)，右移同理。

于是问题就变成了: 有\(N\)个数一开始每个数有个位置，现在可以花\(A\)的代价把一个数往右移到任意位置(不一定非是整数)，\(B\)的代价把一个数往左移到任意位置，然后求将它们排序的最小代价和！

这个东西又是一个简单的dp，设\(dp[i][j]\) (\(0\le j\le n\))表示前\(i\)个数排好序，第\(i\)个放在区间\([j,j+1)\)内的最小代价，转移非常容易(注意要对不移动的情况单独考虑)，前缀和优化，时间复杂度\(O(N^2)\).

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cassert>

#include<iostream>

#include<algorithm>

#define llong long long

using namespace std;

inline int read()

{

	int x=0; bool f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');

	if(f) return x;

	return -x;

}

const int N = 5000;

const llong INF = 10000000000000000ll;

int p[N+3],pp[N+3];

llong dp[N+3][N+5],sdp[N+3][N+5];

int n; llong arga,argb;

void update(llong &x,llong y) {x = x<y?x:y;}

int main()

{

	scanf("%d%lld%lld",&n,&arga,&argb);

	for(int i=1; i<=n; i++) {scanf("%d",&p[i]); pp[p[i]] = i;}

	for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) dp[i][j] = sdp[i][j] = INF;

	for(int i=0; i<=n; i++) sdp[0][i] = dp[0][i] = 0ll;

	for(int i=1; i<=n; i++)

	{

		for(int j=0; j<=n; j++)

		{

			if(j==pp[i]) {update(dp[i][j],sdp[i-1][j-1]);}

			llong tmp = sdp[i-1][j]+(j<pp[i]?argb:arga);

			update(dp[i][j],tmp);

//			printf("dp[%d][%d]=%lld\n",i,j,dp[i][j]);

		}

		sdp[i][0] = dp[i][0];

		for(int j=1; j<=n; j++) sdp[i][j] = min(sdp[i][j-1],dp[i][j]);

	}

	llong ans = sdp[n][n];

	printf("%lld\n",ans);

	return 0;

}

巴特西

AtCoder AGC032D Rotation Sort (DP)

题目链接

题解

代码

最新文章

热门文章