本文共 1689 字，大约阅读时间需要 5 分钟。

遍历 1 --> sqrt(m) + 1

n - i 是摧毁机器人的花费， k * i - m 是增加能量棒的花费

#include 
   
    using namespace std;const int inf=1e9;int n,m;void solve(){   	scanf("%d%d",&n,&m);	if(n > m)	{   		printf("%d\n",n-m);		return ;	}	int sq = sqrt(m) + 1;	int ans = inf;	for(int i = 1; i <= sq; ++i)	{   		int k = (m + i - 1) / i;// k是 m / i 向上取整  		if(n >= i)// n -> i		{   			ans = min(ans, n - i + k * i - m);			// n - i 是摧毁机器人的花费， k * i - m 是增加能量棒的花费 		}		if(n >= k)// n -> k		{   			ans = min(ans, n - k + k * i - m);		}	}	printf("%d\n", ans);}int main(){   	int T;	scanf("%d",&T);	while(T--) solve();	return 0;}/*33 1210 68 20*/
   

spfa + 完全背包

思路：先用求出1到每个节点的最短路，然后就变成了完全背包问题

#include
   
    using namespace std;typedef long long ll;const int N = 5e3 + 9;int a[N], dis[N], dp[N], vis[N];vector 
    
      v[N];int main(){   	int n, m , t;	cin >> n >> m >> t;	for(int i = 2; i <= n; ++i) scanf("%d", &a[i]);	while(m--)	{   		int x, y;		scanf("%d %d", &x, &y);		v[x].push_back(y);		v[y].push_back(x);	}	for(int i = 2; i <= n; ++i) dis[i] = t + 1;	queue 
     
       q;	q.push(1);	while(!q.empty())	{   		int now = q.front();		q.pop();        vis[now] = 0;		int d = dis[now] + 1;		for(auto x : v[now])			if(dis[x] > d)			{   				dis[x] = d;				q.push(x);                vis[x] = 1;			}	}	for(int i = 2; i <= n; ++i) dis[i] <<= 1;// 来回需要两遍	for(int i = 1; i <= t; ++i)	{      // 根据题意遍历每一个总时间t		dp[i] = dp[i-1];		for(int j=2; j <= n; ++j)// 完全背包从小到大		{   			if(dis[j] <= i)			{   				dp[i] = max(dp[i], a[j] + dp[i - dis[j]]);			}		}	}	for(int i = 1; i <= t; ++i)    {           if(i > 1) cout << " ";        cout << dp[i];    }	return 0;}