SRM 285 DIV1 Hard Distincter

問題 Editorial

問題

数列sequenceが与えられる。
「どれかを1増加させる」「どれかを1減少させる」という操作ができる。なお、マイナスにすることもできる。
最低K個の相違なる数を含ませるようにするとき、操作回数を最小化せよ

• 1 <= |sequence| <= 50
• 1 <= sequence[i] <= 1000
• 1 <= K <= |sequence|

解答

Editorialを見た。
まずソートする。作る数はこの順序を変えなくてもいいらしい(わかってない)。
なのでDPする。(i * この数より大きくする * 残りK)という感じで。数だけ増加させてiを変えないようにすれば状態ごとの処理がO(1)でできる。
数の範囲はたかだか(-|sequence|/2〜1000+|sequence|/2)くらいなのでできる。
他に最小費用流を使う解答もある。フォーラム参照。
可能な数のノードとsequenceのノード間にabs(sequence[i]-x)のコストの辺を張る。辺の容量を1にしてフローをK流せばいい。
計算量が少し大きいが、間に合うらしい。

コメント

順序を変えなくてもいいというのはわかってないけれど、なんとなくそうでありそうだよね。
"相違なる"からフローの容量を連想できる。
普通に解けるべき問題だと思った

コード

#include <vector>
#include <cstring>
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(o) (o).begin(), (o).end()
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<int> vi;  

int dp[55][1201][2][55];
struct Distincter {
	vi s; int n;
	int rec(int i, int x, bool gt, int k) {
		if(x > 1200) return INF;
		if(dp[i][x][gt][k] != -1) return dp[i][x][gt][k];
		int r = INF;
		if(i == n) {
			r = k == 0 ? 0 : INF;
		}else {
			r = min(r, rec(i, x+1, true, k));
			r = min(r, abs(s[i] - x) + rec(i+1, x, false, max(0, k-gt)));
		}
		return dp[i][x][gt][k] = r;
	}
	int disperse(vector <int> s_, int K) {
		s = s_, n = s.size(), sort(all(s));
		rep(i, n) s[i] += 55;
		mset(dp, -1);
		return rec(0, 0, true, K);
	}
};