专栏文章

P14508 猜数游戏 guess

qqqqaaazzz_qwq
P14508题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min7t46x
此快照首次捕获于
2025/12/01 21:58
3 个月前
此快照最后确认于
2025/12/01 21:58
3 个月前
查看原文
记 max⁡ai=V\max a_i=V。
目标位置在任何时刻，都一定是可能在一段区间内出现。
一开始是 [1,n][1,n]，当你走进这个区间的时候，就会把区间分成两部分，而目标必定在一部分里面。然后你会发现状态只跟区间长度有关，状态数 Θ(n)\Theta(n)，转移枚举走进去了多长（最多为 VV），就好了。
还要跑个最短路，did_i 表示发生恰好 ii 的位移最小代价是多少。这里只需要考虑 i≤2000i \leq 2000 的情况就行了，因为有一个结论是：如果每一步大小都在 −S∼S-S\sim S 之间，并且总和也在 −S∼S-S \sim S 之间，那么总能够找到一种走路方法，使得走完每一步位置都在 −S∼S-S \sim S 之间。
复杂度 Θ(T(nV+V2))\Theta(T(nV+V^2))。
CPP
#include <bits/stdc++.h>
#define int long long
#define FAST ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
/*
by qqqaaazzz
dis[i] 表示造成了 i 的真实位移的代价 
*/
int n,m;
int a[50010],b[50010];
int f[50010],g[50010];
int D[2010][2010];
int dis[2010];
bool vis[2010];
int is[2010];
int dp[50010];//dp[i] 表示还剩 i 个的时候呢？ 

void solve(){
	cin >> n >> m;
	for (int i=1;i<=m;i++) cin >> a[i];
	for (int i=1;i<=m;i++) cin >> b[i];
	memset(D,0x3f,sizeof(D));
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	for (int i=0;i<=2000;i++){
		for (int j=1;j<=m;j++){
			if(i+a[j]<=2000) D[i][i+a[j]] = min(D[i][i+a[j]],b[j]);
			if(abs(i-a[j])<=2000) D[i][abs(i-a[j])] = min(D[i][abs(i-a[j])],b[j]);
		}
	}
	//跑 Dij 
	dis[0] = 0;
	for (int i=0;i<=2000;i++){
		int k = -1;
		for (int j=0;j<=2000;j++){
			if(!vis[j]&&(k==-1||dis[j]<dis[k])) k = j;
		}
		vis[k] = 1;
		for (int j=0;j<=2000;j++){
			dis[j] = min(dis[j],dis[k]+D[k][j]);
		}
	}
	memset(dp,0x3f,sizeof(dp));
	dp[1] = 0;
	for (int i=2;i<=n;i++){
		for (int j=1;j<=min(i-1,2000ll);j++){
			dp[i] = min(dp[i],max(dp[j],dp[i-j])+dis[j]);
		}
	}
	cout << (dp[n]>1e18? -1:dp[n]) << "\n";
}

signed main()
{
	FAST;
	int c,t;
	cin >> c >> t;
	while(t--) solve();
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...