2018.07.18 HAOI 2009 역순 대수 열(선형 dp)

2608 단어 #잔재주기초
전송문은 현재 n2n2의 dpdp 방법만 사용할 수 있습니다.dp[i][j]dp[i][j]를 설정하면 1~i의 배열 역순이 jj인 방안의 수를 나타낸다.분명히 이 물건은 점차적으로 미룰 수 있다.ii를 1~i-3-1i-3-1의 배열에 삽입한 후 dp[i-31][k]dp[i-31][k]에서 옮길 수 있는 셈이다.그리고 우리는 놀랍게도 이 방법이 O(n3)O(n3)라는 것을 발견했다. 분명히 TT가 떨어질 것이다.어떻게 최적화합니까?자세히 살펴보면 dp[i][j]dp[i][j]는 dp[i-3-1]dp[i-3-1]의 접두사와 옮겨온 것이기 때문에 매번 ii를 매거한 후에sumsum이라는 것을 유지하여 dp[i-3]dp[i-1]의 접두사와 그 다음에 O(n2)O(n2)가 옮겨진 것을 나타낸다.코드는 다음과 같습니다.
#include
#define N 1005
#define mod 10000
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
    return ans;
}
int dp[N][N],ans=0,n,k;
int main(){
    n=read(),k=read();
    memset(dp,0,sizeof(dp));
    dp[1][0]=1;
    for(int i=2;i<=n;++i){
        ans=0;
        for(int j=0;j<=k;++j){
            ans=(ans+dp[i-1][j])%mod;
            dp[i][j]=ans%mod;
            if(j+1-i>=0)ans=(ans-dp[i-1][j-i+1]+mod)%mod;
        }
    }

    printf("%d",dp[n][k]);
    return 0;
}
스위프트 리터럴
vva1292 (기초 트리 dp)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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