从P1179 数字统计过来的qwq
by 决心少年 @ 2019-11-11 21:29:00
@[血祭少年](/user/215603) 这是数位DP，建议学习数位dp之后再来AC
by zyywzw @ 2019-11-11 21:31:02
数位DP。。。
数位DP?我学过DP
@[zyywzw](/user/28906)
by 决心少年 @ 2019-11-11 22:13:06
```cpp
#include<iostream>
using namespace std;
// n-5 最长上升子序列
//a[1] a[2] a[3] a[4] a[5]
// 5 8 2 10 40
//1+3=4 1+2=3 1+2=3 1+1=2 1
// f[1] f[2] f[3] f[4] f[5]
//a[1] a[2] a[3] a[4] a[5]
// 5 8 2 10 40
// 1 1+1=2 1+0 1+2=3 1+3=4
// f[1] f[2] f[3] f[4] f[5]
int n,a[10001],f[10001];
void read()
{ int i,j,max1,k;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
//填记忆数组
f[n]=1;//边界 最一个人
for(i=n-1;i>=1;i--)//从后向前填
{ max1=0;//没有人合作很伤心0
for(j=i+1;j<=n;j++)//扫描合作伙伴i+1...<=n
if(a[i]<a[j]&&f[j]>max1 )//愿意合作原始数据，潜力最大
max1=f[j];//记合伙人最大潜力值
f[i]=1+max1;//自己1+潜力最大的合伙人的潜力
}
max1=0;
for(i=1;i<=n;i++)
if(f[i]>max1)
max1=f[i];
cout<<"最长上升子序列："<<max1<<endl;
f[1]=1;//先填第一个人
for(i=2;i<=n;i++)
{ max1=0;
for(j=1;j<=i-1;j++)//合伙人
if(a[i]>a[j]&&f[j]>max1)
max1=f[j];
f[i]=1+max1;
}
max1=0;
for(i=1;i<=n;i++)
if(f[i]>max1)
max1=f[i];
cout<<"最长上升子序列："<<max1<<endl;
}
}
int main()
{
}
```
呐，最长上升子序列 DP
~~跟数位DP有关系吗？~~
@[zyywzw](/user/28906)
by 决心少年 @ 2019-11-11 22:19:28
@[血祭少年](/user/215603) 没有，数位DP是一种本质为记搜，通过对数字按位处理得到答案的DP，如果没有tg以及省选需求可以不用学习
by zyywzw @ 2019-11-12 07:01:36
@[血祭少年](/user/215603) 100%的数据中，a<=b<=10^12
你这个时间复杂度太大，推荐使用~~数位DP（我自己都没学过）~~ 小学奥数方法
by Presentation_Emitter @ 2020-01-17 13:30:55
@[血祭少年](/user/215603)
谁给你暴力的勇气的，要是随便暴力就过了，ZJOI会出这种题吗？
你没看看标签吗？
不过这道数位DP还是比较简单的
by 光明正大 @ 2020-03-10 20:16:13
你以为是 梦中的统计 这道题，顺便把这道红题A了
by aZhouyiyulg1 @ 2020-03-22 14:48:59
数位DP，DFS，我做的时候裂开了
by FishingStar @ 2020-07-23 19:40:23
不知道建议上度娘，里面讲的很清楚
by FishingStar @ 2020-07-23 19:40:45