C. Jump and treat (DP + monotonic queue optimization)

JSCPC

Problem

Give an example from 0 Start , The length is n+1 A sequence , from 1 To n Each point has a certain value of gold coins a[i]（ Positive but negative ）. from 0 Start at node , You can jump no more than each time p Nodes , Jump to the node i Go up （ Assuming that the i Node No. jumps to j Node No ,$i<j,j-i\le p$ ）. Yes q A asked , One at a time x（$1\le x\le n$）, You can only jump to x On the node of multiples （ If the node number is less than n Words , Can only jump to x On the integer multiple node of . When jumping to less than or equal to n The last x On the integer multiple node of , Just take the last step out n, And this step does not exceed p that will do ）, meanwhile , Each jump cannot exceed p, And must eventually jump to greater than n On the node of ： Ask how much gold coins you can collect . If you can't jump to greater than n On the node of , The output "Noob".

Solution

1. State means ：dp[i] It means to jump to the node i The most valuable gold coin that can be collected on the .
2. State shift ：$dp[i]=max(dp[j])+a[i](i\%x=0,j\%x=0,i-j\le p)$
   Can be maintained with monotonic queues that can be transferred to state i Several states of .
3. Be careful ： Finally, you must jump to greater than n Node , The last state should be n + 1, Not the last x On the integer multiple node of （ n / x * x + x）. And the two states are not equivalent .
   for example ： n = 10,p = 5, x = 2.
   When the last state is n + 1 when （11）, Can be dp[6],dp[8],dp[10] The biggest one in the transfer .
   and , The last state is n / x * x + x when （12）, Can be dp[8],dp[10] The biggest one in the transfer .
   obviously , The two cases are not equivalent , Pay special attention to .

Code

const int N = 2e6 + 6;
ll dp[N];
ll a[N];
unordered_map<ll, ll>mp;

int main()
{
    
	IOS;
	int n, q, p; cin >> n >> q >> p;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	while (q--)
	{
    
		deque<int> q;
		int x; cin >> x;

		if (mp.count(x))
		{
    
			cout << mp[x] << endl;
			continue;
		}

		if (x > p) cout << "Noob\n";
		else
		{
    
			dp[0] = 0;
			q.push_back(0);
			vector<int>b;
			b.push_back(0);
			for (int i = x; i <= n; i += x)
				b.push_back(i);
			b.push_back(n + 1);// Be careful ： In this question n You can only jump within x Multiple ,n It can not be x Multiple , So it can't be written n / x * x + x
			for (int i = 1; i < sz(b); i++)
			{
    
				while (q.empty() == 0 && b[i] - b[q.front()] > p) q.pop_front();
				dp[i] = dp[q.front()] + a[b[i]];
				while (q.empty() == 0 && dp[q.back()] <= dp[i]) q.pop_back();
				q.push_back(i);
			}

			mp[x] = dp[sz(b) - 1];
			cout << mp[x] << endl;
		}
	}

	return 0;
}

Tips

Be careful ： Read the questions carefully , The last state of this question is especially detailed .. It's also crucial