HDU 5459 Jesus Is Here(DP)

1255 단어
DP는 답안을 기록하고 DP를 업데이트할 때 각 cff에서 문자열의 끝까지의 길이와pos, 그리고 각 cff에서 문자열의 시작까지의 길이와를 기록한 다음에 각 문자열의 cff의 개수 cnt와 문자열의 길이len을 기록한 다음에 함부로 하면 된다.
#pragma warning(disable:4996)
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 201320;
const LL mod = 530600414;
LL dp[N], pre[N], pos[N], cnt[N], len[N];

void work(){
    dp[3] = dp[4] = 0;
    pre[3] = 0; pre[4] = 2;
    pos[3] = 3; pos[4] = 3;
    cnt[3] = cnt[4] = 1;
    len[3] = 3; len[4] = 5;

    for (int i = 5; i < N; i++){
        len[i] = (len[i - 1] + len[i - 2]) % mod;
        cnt[i] = (cnt[i - 1] + cnt[i - 2]) % mod;
        pos[i] = (pos[i - 1] + pos[i - 2] + cnt[i - 2] * len[i - 1]) % mod;
        pre[i] = (pre[i - 2] + pre[i - 1] + cnt[i - 1] * len[i - 2]) % mod;
        dp[i] = (dp[i - 1] + dp[i - 2] + pos[i - 2] * cnt[i - 1] + pre[i - 1] * cnt[i - 2]) % mod;
    }

}

int main(){
    work();
    int T; scanf("%d", &T);
    int kase = 1;
    while (T--){
        int n; scanf("%d", &n);
        printf("Case #%d: %lld
", kase++, dp[n]); } return 0; }

좋은 웹페이지 즐겨찾기