题解：AT_abc417_d [ABC417D] Takahashi's Expectation

~~我不会告诉你这道题比第五题难。~~

首先，暴力模拟肯定不行，因为时间复杂度会达到

\mathcal O(nq)

，必然超时。而我们发现

p

、

a

、

b

数组最大都只有五百，而

n

也只有一万，这启示我们用

\mathcal O(np)

的算法。

再观察一下，我们会发现如果第

i

次之前的心情小于

p_i

，那么他之后的心情永远不会超过一千，因为如果他的心情超过

p_i

（之后我们暂时默认

p_i

都为五百），那他的心情一定会疯狂下降，直到跌入五百大关。之后心情会上升，但最大情况下，此时心情为五百，

a_i

也为五百，那它的心情达到一千，之后必然会掉，因为这必然会超过

p_{i+1}

。接下来回到全局，如果高桥的初始心情超过

p_1

，那他的心情就会一直掉，直到掉进五百大关，再遵循情况一，心情在零到一千间上下起伏。所以我们把情况分成两部分：一直掉的阶段，上下起伏的阶段。

上下起伏的阶段容易实现。我们设

dp_{i_j}

为从第

i

个礼物开始拿，一直拿到最后一个。而拿之前的心情为

j

时的最终心情。递推式极其简单：当

j \le p_i

时，

dp_{i_j}=dp_{i+1_{j+a_i}}

，因为他拿了这个后，相当于从第

i+1

个礼物开始拿，此时心情为

j+a_i

的最终心情；否则

j>p_i

时，

dp_{i_j}=dp_{i+1_{\max(0,j-b_i)}}

，因为他拿了这个后，相当于从第

i+1

个礼物开始拿，此时心情为

\max(0,j-b_i)

的最终心情（因为心情是要大于等于零的）。

至于初始状态，把所有

dp_{n+1_i}

的位置初始化成

i

即可。

接下来我们看一直下降的阶段。在此之前，我们设

s_i=\sum_1^i b_i

，也就是前缀和。而我们要找的就是第一个

x-s_{i-1} \le p_i

的位置。因为从

i

点开始（包括这个点），它就进入第二阶段了，结果就是刚才预处理出的结果了。不过显然暴力不行；而看到这种，你可能第一时间想到二分，然而很遗憾，这玩意不满足单调性。不过好在

s_i

不会太大，我们可以换一种思路。

首先，我们设

f_i

为满足

s_{j-1}+p_j=i

中最小的

j

的值。这很容易预处理；然后我们对

f_i

从后往前做一次后缀最小值，然后

f_i

的值就变成了

s_{j-1}+p_j \ge i

中最小的

j

的值。而在查询的循环中原先找到的那个

i

，就可以替换成

f_x

了，时间复杂度一下子降到了

\mathcal O(1)

。

还有，如果

x

减去前

n-1

个

b_i

还大于

p_n

，就意味着没有经历第二阶段，要特判输出。

代码：

CPP

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=1e4+10,M=1000; 
//dp_i_j 从第i个物品开始拿，此时心情为j的最终值 
int p[N],a[N],b[N],s[N],dp[N][M+10],f[N*505+10]; //那些数组
signed main(){
	ios::sync_with_stdio(0); //快读
	cin.tie(0),cout.tie(0);
	int n,q;
	cin>>n;
	for(int i=0;i<=n*505+1;i++) f[i]=1e18; //初始化成最大值
	for(int i=1;i<=n;i++){
		cin>>p[i]>>a[i]>>b[i];
		s[i]=s[i-1]+b[i];
		f[s[i-1]+p[i]]=min(f[s[i-1]+p[i]],i); //初始化f数组
	}
	for(int i=n*505;i>=0;i--) f[i]=min(f[i],f[i+1]);  //后缀最小值
	for(int j=1;j<=M;j++) dp[n+1][j]=j; //dp预处理
	for(int i=n;i>=1;i--){
		for(int j=0;j<=M;j++){
			if(j<=p[i]) dp[i][j]=dp[i+1][j+a[i]];
			else dp[i][j]=dp[i+1][max(0ll,j-b[i])]; //两种情况
		}
	}
	cin>>q;
	while(q--){
		int x;
		cin>>x;
		if(x-s[n-1]>p[n]) cout<<max(0ll,x-s[n])<<endl; //特判
		else cout<<dp[f[x]][max(0ll,x-s[f[x]-1])]<<endl; //输出答案
	}
	//n<=p_x+s_x
	return 0;
}

时间复杂度可以认为是预处理

\mathcal O(n)

乘一个一千左右的大常数；查询

\mathcal O(q)

。反正能过。

最后，再次~~无耻地~~求过。

题解：AT_abc417_d [ABC417D] Takahashi's Expectation

文章操作

相关推荐

评论

题解：AT_abc417_d [ABC417D] Takahashi's Expectation