#46 delete（动态规划+树状数组）
标签：delete set operator || namespace fine class 二维 ems
二维的dp非常显然，但这也没有什么优化的余地了。
注意到最后的方案中只有产生贡献的位置是有用的，剩下的部分可以在该范围内任意选取。
所以我们考虑设f[i]为i号位最后产生贡献的答案，则f[i]=max{f[j]+1} (i-j>=a[i]-a[j],a[i]>a[j])。
观察这个限制，即为i-a[i]>=j-a[j]且a[i]>a[j]，以及i>j。可以发现这里i>j的限制是可以被前两个限制所包含的。于是我们考虑换个顺序dp，按照a[i]从小到大来。树状数组维护即可。
至于删数数量，只需要保证i-a[i]
#include
#include
#include
#include
#include
#include
using namespace std;
int read()
{
int x=0,f=1;char c=getchar();
while (c‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();}
while (c>=‘0‘&&c‘9‘) x=(x1)+(x3)+(c^48),c=getchar();
return x*f;
}
#define N 1000010
int n,m,tree[N];
struct data
{
int i,x,ans;
bool operator const data&a) const
{
return xa.x;
}
}a[N];
void ins(int k,int x){while (kk;}
int query(int k){int s=0;while (k) s=max(tree[k],s),k-=k&-k;return s;}
int main()
{
#ifndef ONLINE_JUDGE
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),m=read();
for (int i=1;i)
a[i].x=read(),a[i].i=i,a[i].ans=-N;
sort(a+1,a+n+1);
memset(tree,200,sizeof(tree));
ins(1,0);
for (int i=1;in;)
{
int t=i-1;
while (t1].x==a[i].x)
{
t++;
if (a[t].i>=a[t].x) a[t].ans=query(a[t].i-a[t].x+1)+1;
}
while (it)
{
if (a[i].i>=a[i].x) ins(a[i].i-a[i].x+1,a[i].ans);
i++;
}
}
for (int i=1;i)
if (a[i].i-a[i].x0].ans=max(a[0].ans,a[i].ans);
cout0].ans;
return 0;
}
#46 delete（动态规划+树状数组）
标签：delete set operator || namespace fine class 二维 ems
原文地址：https://www.cnblogs.com/Gloid/p/9690434.html
评论