#C241125C. 新月争霸

标签（Label）

• 动态规划
• 根号分治

网址（Website）

题目详情 - 新月争霸 - Super

题解 - 新月争霸 - Super

题目（Problem）

输入数据 1

4 1
3 2
4 4
5 6
1 6

输出数据 1

9

样例2

见选手目录下的 $xinyue/xinyue2.in$ 与 $xinyue/xinyue2.ans$。

该样例数据满足子任务 2 的限制。

样例3

见选手目录下的 $xinyue/xinyue3.in$ 与 $xinyue/xinyue3.ans$。

该样例数据满足子任务 3 的限制。

样例4

见选手目录下的 $xinyue/xinyue4.in$ 与 $xinyue/xinyue4.ans$。

该样例数据满足子任务 4 的限制。

样例5

见选手目录下的 $xinyue/xinyue5.in$ 与 $xinyue/xinyue5.ans$。

该样例数据满足子任务 5 的限制。

样例6

见选手目录下的 $xinyue/xinyue6.in$ 与 $xinyue/xinyue6.ans$。

该样例数据满足子任务 6 的限制。

题解（Solution）

出题者题解

代码（Code）

15分

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a) For(i,1,n) cerr<<a[i]<<' ';cerr<<' ';
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar('0'+x);
	else write(x/10), putchar(x%10+'0');
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 1012345;
bool ST;

int a[N],h[N];
int n;

namespace S1{
	inline bool check(){
		if(n<=10) return true;
		For(i,1,n-1) if(a[i]<=a[i+1] || h[i]>=h[i+1]) return false;
		return true;
	}
	bitset<N> vst;
	int ans = inf;
	void dfs(int x,int dmg,int co){
		if(x==n+1) return ans=min(ans,co),void();
		if(co >= ans) return;
		For(i,1,n){
			if(!vst[i]){
				vst[i] = true;
				int ht = a[i] * ((h[i]-1)/dmg);
				if(dmg >= h[i]) ht=0;
				dfs(x+1,max(dmg,a[i]),co+ht);
				vst[i] = false;
			}
		} 
	}
	inline void Solve(){
		dfs(1,a[0],0), write(ans), putchar('\n');
	}
}

void Solve(){
	n=rd(), a[0]=rd();For(i,1,n) a[i]=rd(),h[i]=rd();
	if(S1::check()) return S1::Solve();
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("xinyue.in","r",stdin);
	freopen("xinyue.out","w",stdout);
	int Tt=1;double Tim = clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}

40分

#include<bits/stdc++.h>
#include<vector>
#include<deque>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) {For(i,1,b) cerr<<a[i]<<' ';cerr<<'\n';}
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 201234;
bool ST;

vector<int> b[N];
int n,atk,mx,as;
int f[N];
P p[N];

void Solve(){
	n=rd(),mx=p[0].x=rd();For(i,1,n) p[i]={rd(),rd()}, mx=max(mx, p[i].x);
	For(i,1,n) as += ((p[i].y-1)/mx)*p[i].x;
	sort(p+1,p+n+1,[&](P x,P y){return x.x < y.x;});
	memset(f, 0x3f, sizeof f), f[0] = 0;
	For(i,1,n) For(j,0,i-1){
		f[i] = min(f[i], f[j] + ((p[i].y-1)/p[j].x)*p[i].x - ((p[i].y-1)/mx)*p[i].x);
	}write(f[n]+as), putchar('\n');
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("xinyue.in","r",stdin);
	freopen("xinyue.out","w",stdout);
	int T = 1;double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}

100分（根号分治）

#include<bits/stdc++.h>
#include<vector>
#include<deque>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) {For(i,1,b) cerr<<a[i]<<' ';cerr<<'\n';}
using namespace std;
#define P pair<int,int>
#define ull long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}constexpr int inf = 0x3f3f3f3f;
constexpr int N = 201234;
bool ST;

vector<int> b[N];
int n,x,mx;

int fa[N];inline int find(int x){
	if(x==fa[x]) return x;
	return fa[x] = find(fa[x]);
}

int st[N],tp;
ull f[N],as;

void Solve(){
	n=rd(),x=rd();For(i,1,n){
		int x=rd(), y=rd();
		b[x].emplace_back(y);
		mx = max(mx, x);
	}
	if(x >= mx){
		For(i,1,mx) for(auto h:b[i]){
			as += (h-1ll)/x*i;
		}return write(as), putchar('\n'), void();
	}
	iota(fa, fa+mx+1, 0);
	memset(f, 0x3f, sizeof f);
	f[x] = 0;For(i,1,x-1) fa[i] = x;
	st[tp=1] = x;
	For(i,x+1,mx){
		for(auto h:b[i]){
			for(int l=1,r; l<=h-1 && l<i; l=r+1){
				r = (h-1) / ((h-1)/l);
				f[i] = min(f[i], f[find(l)] + (ull)((h-1ll)/l - (h-1ll)/mx)*i);
			}
			if(h < i) f[i] = min(f[i], f[find(h)]);
		}
		while(tp && f[i] < f[st[tp]]){
			fa[st[tp--]] = i;
		}st[++tp] = i;
	}as = f[mx];
	For(i,1,mx) for(auto h:b[i]){
		as += (h-1ll)/mx*i;
	}write(as), putchar('\n');
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("xinyue.in","r",stdin);
	freopen("xinyue.out","w",stdout);
	int T = 1;double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}