codeforces 1077F2. Pictures with Kittens (hard version)单调队列+dp

被队友催着上(xun)分(lian),div3挑战一场蓝，大号给基佬紫了，结果从D开始他开始疯狂教我做人？？表演如何AKdiv3????

比赛场上：A 2 分钟，B题蜜汁乱计数，结果想得绕进去了20多分钟，至此GG，C秒出，D。。。还在想怎么做就告诉我二分答案，好那继续秒出。他看F我看E，没思路互换，F题都读了半天，其实就是我YY的题意，然后发现还是没N^3dp的想法，发现并不是区间dp，其实之前我E想到了枚举等差数列的项数，只是发现找不了起点（那不是找终点就好了）。基佬紫：枚举项数啊，我？？？？然后他写完我就发现自己又傻了，rush完，想了5分钟F，发现了如何n^3dp，发现两个人思路一致，然后他1A了，然后我读秒交了两发，wa7,然后他说应该是单调栈优化，，结果真是，，他就这么AK了。。。然后我就睡觉了，第二天晚上，F1交了14发都是WA7，于是看别人的代码，一通胡改完就跑路了。于是今天中午颓废星人开始搞F2，想了一会儿感觉就是维护X个单调队列就好了，注意的是必须开个tmp数组，否则可能用之前已经更新了的更新这个位置，也就是内层两次for，同时未成功转移到的状态不应放入单调队列。然后一开始的写法感到不适，就找了找题解，写起来快多了。PS:我dp真的菜。

#include<bits/stdc++.h>

#define ll long long

#define mp make_pair

#define fi first

#define pb push_back

#define se second

#define rep(i,a,b)for(int i=a;i<=b;i++)

using namespace std;

const int maxn=5005;

deque<pair<int,ll> >q[maxn];

ll a[maxn];

ll dp[maxn][maxn];

ll tmp[maxn];

ll n,k,x;

int main()

{

	memset(dp,-1,sizeof(dp));

	scanf("%lld%lld%lld",&n,&k,&x);

	rep(i,1,n)scanf("%lld",&a[i]);

	q[0].pb(mp(0,0));

	for(int i=1;i<=n;i++)

	{

		memset(tmp,0,sizeof(tmp));

		for(int j=1;j<=x;j++)

		{

			while(!q[j-1].empty()&&q[j-1].front().fi<i-k)q[j-1].pop_front();

			if(!q[j-1].empty())tmp[j]=q[j-1].front().se+a[i];

		}

		for(int j=1;j<=x;j++)

		{

			while(!q[j].empty()&&q[j].back().se<tmp[j])q[j].pop_back();

			if(tmp[j])q[j].push_back(mp(i,tmp[j]));

		}

	}

	ll ans=-1;

	while(!q[x].empty()&&q[x].front().fi<=n-k)q[x].pop_front();

	if(!q[x].empty())ans=q[x].front().se;

	if(ans>0)cout<<ans<<"\n";

	else cout<<-1<<"\n";

}

巴特西

codeforces 1077F2. Pictures with Kittens (hard version)单调队列+dp

最新文章

热门文章