@[The_Shadow_Dragon](/user/848964) 为什么用树状数组
by yimuhua @ 2023-01-30 14:51:37
线性dp应该可以，但老师说用树状数组写这道题
by hzoi_Shadow @ 2023-01-30 14:51:48
@[ACACACACACACACACACAC](/user/374330) 老师要求的（虽然没什么人听）
by hzoi_Shadow @ 2023-01-30 14:52:12
@[The_Shadow_Dragon](/user/848964) 怎么能线性dp的啊
by yimuhua @ 2023-01-30 14:54:04
@[The_Shadow_Dragon](/user/848964) 只能是树状数组优化n方dp吧
by yimuhua @ 2023-01-30 14:55:14
@[ACACACACACACACACACAC](/user/374330) [题目](https://www.luogu.com.cn/discuss/565080)
```cpp
#include<bits/stdc++.h>
using namespace std;
struct student
{
int dp,next,s;
}a[1001];
void print(int x)
{
if(x==0)
{
return;
}
else
{
print(a[x].next);
cout<<a[x].s<<" ";
}
}
int main()
{
int n=1,i,j,k,sum,num,ans=0;
while(cin>>a[n].s)
{
n++;
}
n--;
for(i=1;i<=n;i++)
{
sum=0;
k=0;
for(j=1;j<=n;j++)
{
if(a[j].s<a[i].s&&sum<a[j].dp)
{
sum=a[j].dp;
k=j;
}
}
a[i].dp=sum+1;
a[i].next=k;
if(ans<a[i].dp)
{
ans=a[i].dp;
num=i;
}
}
cout<<"max="<<ans<<endl;
print(num);
return 0;
}
by hzoi_Shadow @ 2023-01-30 14:58:47
线性做不到吧，树状数组倒是可以优化到 $nlogn$
by Y2y7m @ 2023-01-30 15:00:47
@[The_Shadow_Dragon](/user/848964) 这就是n方dp啊
by yimuhua @ 2023-01-30 15:01:19
@[Y2y7m](/user/377440) 应该只能 $n\log n$，用数据结构优化dp或是二分加贪心
by yimuhua @ 2023-01-30 15:02:07
@[The_Shadow_Dragon](/user/848964)
好像可以吧，感觉是用求逆序对的思想。
你开一个值域大小的树状数组。
然后对于当前的数，去找比他小的 $i$ 的 dp 值去更新。
也是nlogn的吧？
by _JF_ @ 2023-01-30 15:04:26