1759.最長上昇サブシーケンス[動的計画]
5327 ワード
1759:最長上昇サブシーケンス
構想
法一:検索
時間の複雑さはO(2^n)で、期待に背かない・・・タイムアウトしました.
法二:動的計画
時間複雑度O((n^2)/2)、
順調AC!
: 2000ms : 65536kB
bi, b1 < b2 < ... < bS , 。
(a1, a2, ..., aN), (ai1, ai2, ..., aiK), 1 <= i1 < i2 < ... < iK <= N。
, (1, 7, 3, 5, 9, 4, 8), , (1, 7), (3, 4, 8) 。 4, (1, 3, 5, 8).
, , 。
N (1 <= N <= 1000)。 N , 0 10000。
。
7
1 7 3 5 9 4 8
4
構想
法一:検索
#include
using namespace std;
int a[1005],b[1005],c[1005],t1,s;
void dfs(int i,int t)//
{
if(i==1)//
{
b[1]=a[1];
dfs(i+1,t+1);
b[1]=0;
dfs(i+1,t);
}
if(i==s+1)// ,
{
if(t>t1)
t1=t;
return;
}
if(a[i]>b[t])//
{
b[t+1]=a[i];
dfs(i+1,t+1);
b[t+1]=0;
}
dfs(i+1,t);
}
int main()
{
cin>>s;
for(int i=1;i<=s;i++)
cin>>a[i];
dfs(1,0);
cout<return 0;
}
時間の複雑さはO(2^n)で、期待に背かない・・・タイムアウトしました.
法二:動的計画
#include
using namespace std;
int main()
{
int b[1005]={}/* a[1]~a[i] */,a[1005]/* */,i,s,j;
cin>>s;
for(i=1;i<=s;i++)
cin>>a[i];
for(i=1;i<=s;i++)
{
for(j=1;j/* , */
{
if(a[i]>a[j])
b[i]=max(b[j],b[i]);
}
b[i]++;//
}
sort(b+1,b+s+1);// , , algorithm 。
cout<return 0;
}
時間複雑度O((n^2)/2)、
順調AC!