P1637 三元上升子序列

​
P1637 三元上升子序列
UVA12983 The Battle of Chibi

给定一个长度为n的序列，求其包含的m元单调上升子序列个数。
见求LIS思DP。导弹拦截那种题，开f[结尾编号]=序列长度，信息量不够，考虑定义f[序列长度][结尾编号] =序列个数。

状态转移：f[i][j]=∑f[i−1][k],1<=k

这样做的时间复杂度为O(n2∗m)O(n^2*m)O(n2∗m)

得想办法在更短时间内统计出∑f[i−1][k]\sum f[i-1][k]∑f[i−1][k],树状数组或者线段树都可以实现在O(logn)O(log n)O(logn)内的区间统计。

先离散化，将a[]的分布集中起来，以a[k]为下标储存f[i-1][k]的值。

此时针对状态转移方程写两层循环：外层循环枚举长度，每次枚举到一个长度都重置一下树状数组c[]。{内层枚举序列结尾坐标，此前已将f[i-1][k]增加到树状数组中，此时只需用树状数求和即可。然后把f[i-1][j]加到树状数组中，这个值只会更新到比a[j]大的数（对应状态转移方程里的a[k]

#include
using namespace std;
#define ll long long
const int N=30010;
ll n,f[4][N],a[N],b[N],c[N],ans;ll lowbit(ll x) { return x&(-x);}void update(ll p,ll v)
{for(int i=p;i<=n;i+=lowbit(i))c[i]+=v;
} ll ask(int p)
{ll sum=0;for(int i=p;i;i-=lowbit(i))sum+=c[i];return sum;
}int main()
{cin>>n;for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i]=a[i];sort(b+1,b+n+1);unique(b+1,b+n+1)-(b+1);for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+n+1,a[i])-b;//二分查找在数组中的位置f[1][i]=1;//初始化：长度唯一，本身为结尾}//离散化结束，初始化结束，准备工作完成for(int i=2;i<=3;i++)//枚举长度{memset(c,0,sizeof(c));//重置树状数组for(int j=1;j<=n;j++){f[i][j]=ask(a[j]-1);//求和update(a[j],f[i-1][j]);//更新}}for(int i=1;i<=n;i++)ans+=f[3][i];cout<

#include
using namespace std;
const int N=3010;
int f[N][N];
int n,a[N],b[N];
int main()
{cin>>n;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){f[i][j]=f[i-1][j];if(a[i]==b[j]){int maxv=1;for (int k=1;kb[k]) maxv=max(maxv, f[i - 1][k] + 1);f[i][j]=max(f[i][j], maxv);}}int ans=0;for(int j=1;j<=n;j++)ans=max(ans,f[n][j]);cout<

#include
using namespace std;
const int N=3010;
int f[N][N];//a1~ai,b1~bj可以构成的以bj结尾的LCIS的长度
int n,a[N],b[N],ans=0,m;
int main()
{cin>>n;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);for(int i=1;i<=n;i++){int val=0;//(i,0)的LCIS长度//i固定，b1->bn时LCIS长度一定是单调递增的for(int j=1;j<=n;j++){if(a[i]==b[j]) f[i][j]=val+1;//遍历到一个ai、bj相同的位置，长度++else f[i][j]=f[i-1][j];//不相等，直接继承(i-1,j)的长度if(b[j]a[i])一定不会影响到LCIS的长度}}for(int j=1;j<=n;j++)//找出所有以bj结尾的LCIS中长度最大的ans=max(ans,f[n][j]);cout<

#include
using namespace std;
const int N=3010;
int f[N];//a1~ai,b1~bj可以构成的以bj结尾的LCIS的长度
int n,a[N],b[N],ans=0,m;
int main()
{cin>>n;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);for(int i=1;i<=n;i++){int val=0;//(i,0)的LCIS长度//i固定，b1->bn时LCIS长度一定是单调递增的for(int j=1;j<=n;j++){if(a[i]==b[j]) f[j]=val+1;//遍历到一个ai、bj相同的位置，长度++if(b[j]a[i])一定不会影响到LCIS的长度}}for(int j=1;j<=n;j++)//找出所有以bj结尾的LCIS中长度最大的ans=max(ans,f[j]);cout<

#include
using namespace std;
const int N=3010;
int f[N];//a1~ai,b1~bj可以构成的以bj结尾的LCIS的长度
int n,a[N],b[N],ans[N],m,scheme[N],p;
int main()
{cin>>n;for(int i=1;i<=n;i++)scanf("%d",&a[i]);cin>>m;for(int i=1;i<=m;i++)scanf("%d",&b[i]);for(int i=1;i<=n;i++){int id=0;//i固定，b1->bn时LCIS长度一定是单调递增的for(int j=1;j<=m;j++){if(a[i]==b[j]) f[j]=f[id]+1,scheme[j]=id;//遍历到一个ai、bj相同的位置，长度++,记录下j前面一个位置是id if(b[j]f[p]) p=i;//找出所有以bj结尾的LCIS中长度最大的printf("%d\n",f[p]);int top=0;while(f[p]--) {ans[++top]=b[p];id=scheme[p];//从后往前倒出来 }for(int i=top;i;i--)printf("%d ",ans[i]);//输出方案前需要记录return 0;
}