Gym – 100507G G. The Debut Album 数位dp+内存优化

G - The Debut Album 数位dp+内存优化

 Source

Gym - 100507G

ACM ICPC 2014-2015. NEERC. Eastern Subregional Contest
Yekaterinburg, October 11, 2014

My Solution

题意：最多连续a个1，最多连续b个2，构造出长度为n的字符串的个数。

数位dp+内存优化
dpij0表示在访问字符串的第i为连续j个1时的方案数，dpij1表示在访问字符串的第i为连续j个2时的方案数，sum[i][0]、sum[i][1]表示上访问完第i位时的总方案数。
对位1、2分别对于1~a, 1~b,  当j等于1时上一位必定是2故 dp[i][j][0] = sum[i-1][1]，其它时候当dpi[j-1][0] 存在时 dpij0 = d[i-1][j-1][0];
然后5e4*300*2 * 32 / 8 / 1024 / 1024 ≈ 70+MB，确实MLE， 故每次只保存上一次的状态和当前状态，转移完以后用当前状态覆盖当上一次状态的位置，然后空出新位置。
复杂度 O(n * (a + b))

#include 
#include 

using namespace std;
typedef long long LL;
const int maxn = 5e4 + 2;
const int MOD = 1e9 + 7;

inline int mod(const int &x)
{
    return x - x / MOD * MOD;
}

int dp[6][302][2], sum[6][2];

int main()
{
    #ifdef LOCAL
    freopen("g.txt", "r", stdin);
    //freopen("g.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, a, b, i, j;
    cin >> n >> a >> b;
    for(i = 1; i <= n; i++){
        if(i == 1) {
            dp[1][1][0] = 1;
            dp[1][1][1] = 1;
            sum[1][0] = sum[1][1] = 1;
            continue;
        }
        for(j = 1; j <= a; j++){
            if(j == 1){
                dp[2][j][0] = sum[1][1];
                sum[2][0] = mod(sum[2][0] + dp[2][j][0]);
            }
            else if(dp[1][j-1][0]){
                dp[2][j][0] = dp[1][j-1][0];
                sum[2][0] = mod(sum[2][0] + dp[2][j][0]);
            }
            else break;

        }
        for(j = 1; j <= b; j++){
            if(j == 1){
                dp[2][j][1] = sum[1][0];
                sum[2][1] = mod(sum[2][1] + dp[2][j][1]);
            }
            else if(dp[1][j-1][1]){
                dp[2][j][1] = dp[1][j-1][1];
                sum[2][1] = mod(sum[2][1] + dp[2][j][1]);
            }
            else break;
        }
        for(j = 1; j <= a; j++){dp[1][j][0] = dp[2][j][0]; dp[2][j][0] = 0; } sum[1][0] = sum[2][0]; sum[2][0] = 0;
        for(j = 1; j <= b; j++){dp[1][j][1] = dp[2][j][1]; dp[2][j][1] = 0; } sum[1][1] = sum[2][1]; sum[2][1] = 0;
    }
    cout << mod(sum[1][0] + sum[1][1]) << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx