NC21313 美丽序列

本文主要是介绍NC21313 美丽序列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

状态表示\(f[i][j][l][sum]\) 从前\(i\)个选，且第\(i\)个数为\(j\)，加上j后的递减序列的长度为\(l\)，以及当前所有数的总和为\(sum\)的方案数
状态转移

\[ if (j >= k) \quad f[i][j][1][sum + j] = (f[i][j][1][sum + j] + f[i - 1][k][1][sum] + f[i - 1][k][2][sum]) % MOD; \\ else \quad f[i][j][2][sum + j] = (f[i][j][2][sum + j] + f[i - 1][k][1][sum]) % MOD; \]

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
int n;
int a[50];
LL f[45][45][5][1610];  
int main() {
	IOS;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    if (a[1] == -1) {
        for (int i = 0; i <= 40; i ++ )
            f[1][i][1][i] = 1;
    }
    else    f[1][a[1]][1][a[1]] = 1;
    for (int i = 2; i <= n; i ++ ) {
        if (a[i] == -1) {
            for (int j = 0; j <= 40; j ++ ) {
                for (int k = 0; k <= 40; k ++ ) {
                    int max_sum = 1600 - j;
                    for (int sum = j * (i - 1); sum <= max_sum; sum ++ ) {
                        if (j >= k) 
                            f[i][j][1][sum + j] = (f[i][j][1][sum + j] + f[i - 1][k][1][sum] + f[i - 1][k][2][sum]) % MOD;
                        else    
                            f[i][j][2][sum + j] = (f[i][j][2][sum + j] + f[i - 1][k][1][sum]) % MOD;
                    }
                }
            }
        }
        else {
            int j = a[i];
            for (int k = 0; k <= 40; k ++ ) {
                int max_sum = 1600 - j;
                for (int sum = j * (i - 1); sum <= max_sum; sum ++ ) {
                    if (j >= k) 
                        f[i][j][1][sum + j] = (f[i][j][1][sum + j] + f[i - 1][k][1][sum] + f[i - 1][k][2][sum]) % MOD;
                    else    
                        f[i][j][2][sum + j] = (f[i][j][2][sum + j] + f[i - 1][k][1][sum]) % MOD;
                }
            }
        }
    }
    LL res = 0;
    for (int sum = 0; sum <= 1600; sum ++ ) {
        for (int i = 0; i <= 40; i ++ ) {
            res = (res + f[n][i][1][sum]) % MOD;
            res = (res + f[n][i][2][sum]) % MOD;
        }
    }
    cout << res << endl;
 	return 0;
}

这篇关于NC21313 美丽序列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！