題解DTOJ#1071.王様C kingdom

My Luogu Spaceへようこそ.
【テーマ大意】
いくつかの正の整数は、これらの正の整数の和が50000 50000 50000を超えないことを保証しています.今、これらの数の和が4 4 4と7 7 7だけで構成されるように、任意に数を取り出す必要があります.構成できない場合は"-1"を出力します.
【問題解】
バイナリデポジション最適化dp
最初は素朴なdp:dp[j]=m i n(dp[j],dp[j−s[i]+1)dp[j]=min(dp[j],dp[j−s[i]+1)dp[j]=min(dp[j],dp[j−s[i]+1)であり,i i iはこれらの正の整数を列挙し,j j j jはn n nからn−s[i]n−s[i]n−s[i]n−s[i]n−s[i]までの数を列挙した.dpの中の値はこの数を取るには少なくとも何回取る必要があります.
しかし、このような効率は少し足りないので、どのように最適化するかを考えています.
本題で与えられたデータが比較的大きいと,より多くの数字が繰り返されることが分かったが,繰り返された数字は1つ1つdpに持ち込む必要はない.
現在、ある数字が繰り返される回数がk k kであると仮定すると、k k kを1、2、4、8に分けます.1,2,4,8...... 1,2,4,8......,最後のグループは残りの数です.各グループを新しい数字と見なし,これらの数字は元のk k個の数字からなるすべての数を構成することができる.私たちは答えを更新するときに回数にこれらの数字の値を加えるだけでいいです.
これで数字の個数が下がり、効率が向上します.
【コード】

// output format !!!
// long long !!!
#include 
typedef long long LL;
using namespace std;
const int MAXN = 50000+10;
const int INF = 0x3f3f3f3f;

int n, m, ans=INF;
int fa[MAXN], num[MAXN], siz[MAXN], dp[MAXN];
vector<int> S;

int G(int x){
	return fa[x]==x ? x : fa[x]=G(fa[x]);
}
int can(int x){
	while(x){
		int y = x%10;
		if(y!=4 && y!=7) return 0;
		x /= 10;
	}
	return 1;
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; ++i) fa[i]=i, siz[i]=1;
	while(m--){
		int a, b; scanf("%d%d", &a, &b);
		int x=G(a), y=G(b);
		if(x == y) continue;
		fa[y] = x, siz[x] += siz[y];
	}
	for(int i=1; i<=n; ++i)
		if(G(i) == i){
			if(!num[siz[i]]) S.push_back(siz[i]);
			++num[siz[i]];
		}
	memset(dp, INF, sizeof dp);
	dp[0] = 0;
	for(auto i=S.begin(); i!=S.end(); ++i){
		for(int k=1; k<=num[*i]; num[*i]-=k, k<<=1)
			for(int j=n; j>=k*(*i); --j)
				dp[j] = min(dp[j], dp[j-k*(*i)]+k);
		for(int j=n; j>=num[*i]*(*i); --j)
			dp[j] = min(dp[j], dp[j-num[*i]*(*i)]+num[*i]);
	}
	for(int i=1; i<=n; ++i){
		if(dp[i] >= ans) continue;
		if(can(i)) ans = dp[i];
	}
	printf("%d", ans==INF?-1:ans-1);
	return 0;
}