【智障题系列C】序列问题

有条件的LIS(N^2):

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cctype>
using namespace std;
#define maxn 100010
template <class T>
inline void read(T& x){
	char c = getchar();bool flag = false;x = 0;
	while(!isdigit(c)){if(x=='-')flag=true;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	if(flag)x = -x;
}
int n,d;
int a[maxn];
int dp[maxn];
int main(void)
{
//	cin>>n>>d;
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	while(scanf("%d%d",&n,&d)==2)
	{
//		read(n),read(d);
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)read(a[i]);//cin>>a[i];
		dp[1] = 1;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<i;j++)
			{
				if(a[i]>a[j]&&i-j>d)dp[i] = max(dp[i],dp[j]+1);
				else dp[i]= max(dp[i],dp[j]);
			}				
		}
		printf("%d\n",dp[n]);
	}
	return 0;
}

然而由于不会LIS的nlogn做法我有点方，

当时想到用单调队列优化一下的。。。

然而忘了单调队列怎么写了。。

orz。。

然而忘了还可以套线段树来维护，虽然常数大了点，但是1e5是不会T的

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <cmath>  
#include <string>  
#include <map>  
#include <stack>  
#include <vector>  
#include <set>  
#include <queue>  
#pragma comment (linker,"/STACK:102400000,102400000")  
#define maxn 1005  
#define MAXN 100005  
#define OO (1<<31)-1  
#define mod 90003  
#define INF 0x3f3f3f3f  
#define pi acos(-1.0)  
#define eps 1e-6  
typedef long long ll;  
using namespace std;  
  
int n,d,ans;  
int a[MAXN],maxx[MAXN<<2],dp[MAXN];  
  
#define ll long long
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}  
  
int query(int le,int ri,int rt,int x,int y)  
{  
    if(le==x&&ri==y) return maxx[rt];  
    int mid=(le+ri)>>1;  
    if(y<=mid) return query(le,mid,rt<<1,x,y);  
    else if(x>mid) return query(mid+1,ri,rt<<1|1,x,y);  
    else  
    {  
        return max(query(le,mid,rt<<1,x,mid),query(mid+1,ri,rt<<1|1,mid+1,y));  
    }  
}  
void update(int le,int ri,int rt,int x,int y)  
{  
    if(le==ri)  
    {  
        maxx[rt]=max(maxx[rt],y);  
        return ;  
    }  
    int mid=(le+ri)>>1;  
    if(x<=mid) update(le,mid,rt<<1,x,y);  
    else update(mid+1,ri,rt<<1|1,x,y);  
    maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]);  
}  
int main()  
{  
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
    int i,j,t;  
    while(~scanf("%d%d",&n,&d))  
    {  
        memset(maxx,0,sizeof(maxx));  
        ans=0;  
        for(i=1;i<=n;i++)  
        {  
            a[i]=read();  
            a[i]+=2;  
            dp[i]=query(1,100002,1,1,a[i]-1)+1;  
            ans=max(ans,dp[i]);  
            if(i-d>=1) update(1,100002,1,a[i-d],dp[i-d]);  
        }  
        printf("%d\n",ans);  
    }  
    return 0;  
}  

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <cmath>  
#include <string>  
#include <map>  
#include <stack>  
#include <vector>  
#include <set>  
#include <queue>  
#pragma comment (linker,"/STACK:102400000,102400000")  
#define maxn 1005  
#define MAXN 100005  
#define OO (1<<31)-1  
#define mod 90003  
#define INF 0x3f3f3f3f  
#define pi acos(-1.0)  
#define eps 1e-6  
typedef long long ll;  
using namespace std;  
#define ll long long 
int n,d,ans;  
int a[MAXN],c[MAXN],dp[MAXN];  
 
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}  
void solve()  
{  
    int i,j,t;  
    ans=0;  
    memset(c,0x3f,sizeof(c));  
    for(i=1;i<=n;i++)  
    {  
        dp[i]=lower_bound(c+1,c+n+1,a[i])-c;  
        ans=max(ans,dp[i]);  
        j=i-d;  
        if(j>0&&c[dp[j]]>a[j]) c[dp[j]]=a[j];  
    }  
}  
int main()  
{  
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
    int i,j,t;  
    while(~scanf("%d%d",&n,&d))  
    {  
        for(i=1;i<=n;i++)  
        {  
           a[i]=read();
		    //scanf("%d",&a[i]);  
        }  
        solve();  
        printf("%d\n",ans);  
    }  
    return 0;  
}  

glk's code:

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define N 100005
#define cmax(a,b) ((__t=(b))>a?a=__t:1)
int C[N], dp[N], a[N], __t;
void Update(int x, int val) {
	for (; x < N; x += x & -x)
	  cmax(C[x], val);
}
int Query(int x) {
	int ret = 0;
	for (; 0 < x; x -= x & -x)
	  cmax(ret, C[x]);
	return ret;
}
int main() {
	freopen("seq.in", "r", stdin); 
	freopen("seq.out", "w", stdout);
	int n, d, ans;
	while (scanf("%d%d", &n, &d) ^ EOF) {
		for (int i = 1; i <= n; ++i)
		  scanf("%d", a + i);
		memset(C, 0, N << 2); ++d;
		for (int i = 1; i <= d; ++i)
		  dp[i] = 1, Update(a[i]+1, 1);
		ans = 1;
		for (int i = d + 1; i <= n; ++i) {
			Update(a[i-d]+1, dp[i-d]);
			dp[i] = Query(a[i]) + 1;
			cmax(ans, dp[i]);
		}
		printf("%d\n", ans);
	}
	return 0;
}