HDOJ 5542 - The Battle of Chibi [나무 모양 배열, dp]

4358 단어 dp데이터 구조트 리 배열hdu
본론
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=5542
제목 의 대의
시퀀스 A 의 길이 가 M 인 서브 시퀀스 가 몇 개 있 습 니까?
문제 풀이 의 사고 방향.
fi, j f i, j 로 길 이 를 i 로 표시 하고 Aj A j 로 끝 나 는 서열 의 개 수 를 표시 합 니 다.그 다음 에 동태 전이 방정식 이 지난번 에 임 의 한 곳 에서 이동 하고 동태 전이 방정식 을 알 수 있다.
fi,j=∑k우 리 는 나무 모양 의 배열 로 k 를 저장 하고 유지 할 수 있다.
code 
#include
#include
#include
#define N 2010
#define lowbit(x) x&-x
#define BPM 1000000007
using namespace std;
int t[N],a[N],f[N][N],n,m,l,uiqe[N],ans,ts;
void change(int x,int k)
{
    while(x<=l)
    {
        t[x]=(t[x]+k)%BPM;
        x+=lowbit(x);
    }
}
int ask(int x)
{
    int sum=0;
    while(x)
    {
        sum=(sum+t[x])%BPM;
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    scanf("%d",&ts);
    for(int ti=1;ti<=ts;ti++)
    {
        scanf("%d%d",&n,&m);
        a[0]=-2147483647;uiqe[n+1]=a[0];
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),uiqe[i]=a[i];
        sort(uiqe+1,uiqe+2+n);
        l=unique(uiqe+1,uiqe+1+n)-(uiqe+1);
        for(int i=0;i<=n;i++)
            a[i]=lower_bound(uiqe+1,uiqe+1+l,a[i])-uiqe;
        //      
        memset(f,0,sizeof(f));
        f[0][0]=1;ans=0;
        for(int i=1;i<=m;i++){
              memset(t,0,sizeof(t));
            change(a[0],f[i-1][0]);//  
            for(int j=1;j<=n;j++){
                f[i][j]=ask(a[j]-1);//   
                change(a[j],f[i-1][j]);//   
                if(i==m) ans=(ans+f[i][j])%BPM;
            }
          }
          printf("Case #%d: %d
",ti,ans);
    }
}
Spring Cloud Sleuth 필터 무의미 한 호출 추적
[시보쥬 데이즈 2021] 킨톤 게임 라보의 뒷면~ 다튼 편~

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage