Subsequences CodeForces - 597C(트리 배열+dp)

1297 단어 dp
제목: 길이가 n인 서열을 정하고, k를 정하며, 상승 서열의 길이가 k+1인 서열수를 구한다.
사고방식: dp[i][j]는 i개수의 위치를 나타내고 서열 길이가 j의 개수로 상승한다.
dp[i][j] = sum(dp[k][j-1])   (k
직접 삼중 순환의 복잡도는 틀림없이 부족할 것이다
그래서 나무형 수조로 최적화를 해볼게요.

#include
#include
#include
#include
#include
#include

using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int a[maxn];
ll dp[maxn][13];

ll lowbit(int x)
{
    return x&(-x);
}

void add(ll x,ll y,ll d)
{
    while(x0)
    {
        sum += dp[x][y];
        x -= lowbit(x);
    }
    return sum;
}

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d",&a[i]);
    }
    k++;
    memset(dp,0,sizeof(dp));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= min(i+1,k); j++)
        {
            if(j==1)
            {
                add(a[i],1,1);
            }
            else
            {
                ll temp = Sum(a[i]-1,j-1);
                add(a[i],j,temp);
            }
        }
    }
    printf("%lld
",Sum(n,k)); return 0; }

좋은 웹페이지 즐겨찾기