小美的数组构造

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >>n;
    vector<int> a(n);
    int sum = 0;
    
    int mod = 1e9 + 7;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
    }
    vector<vector<long>> dp(n+1, vector<long>(sum + 1));
    dp[0][0] = 1;
    for(int i= 1; i <= n; i++) {
        for(int j = 1; j<= sum; j++) {
            for(int k = 1; k <= j-i +1; k++){
                if(a[i - 1] == k) continue;
                dp[i][j] = (dp[i][j] + dp[i -1][j -k]) % mod;
            }
        }
    }
    
    cout<<dp[n][sum]<<endl;

#include <iostream>
#include <vector>
#include<cmath>
using namespace std;

int main() {

    /*
        思路：
        突破口应该在该位置填充的数
        如果我对该数组进行加一减一操作是满足需求的

        每个数都需要被操作，怎么知道这个数有没有被操作，知道其加减操作次数是否相等就行

        存储方式map
        （i，（pair<a,s>)表示数组种第i个元素进行了a次增加s次减少操作 
        
        有什么简单的方法可以很容易的知道每个元素都变化了呢？否则每次都要比对过于麻烦

        没想到简单的方法

        感觉思路不对，要知道每个元素变化除非开始故意避开，否则怎么知道啊我，就得比对，比对时间复杂度过高，那麽多结果必定超时




        将数组变为一开始就必定不相同的初始分配，然后逐渐试探性增加分配元素数目

        先给所有原本为1的元素分配1
        再给所有元素分配1，保证所有元素均与之前不同
        就会得到一个所有元素与之前元素均不相同的数组，剩余一些自由分配点数

        比如说 2 2 1 4
        初始分配为 1 1 2 1 剩余数为4自由分配，只需保证前面的数和不为初始值就可以
        
        采用动态规划
        k分配给（i，j） = k分配给（i，j-1）+（k-1)分配给（i,j-1)+......+0分配给(i,j-1);前提是均可分配，加判断即可
        
        初始有0分配给k个元素分配方案有1种

        动态规划求出k分配给前n个元素的值即可
    
    */

    //获取元素个数
    int n;
    cin>>n;

    vector<int> oldArr(n,0);
    //新分配数组
    vector<int> newArr(n,0);

    //剩余可自由分配点数
    int k = 0;


    for(int i = 0; i < n ; i++)
    {
        cin>>oldArr[i];
        
        if(oldArr[i]== 1)
        {
            newArr[i]=2;
            // k += oldarr[i]-2;
            --k;
        }
        else
        {
            newArr[i]=1;

            k += oldArr[i]-1;
        }
    }
   
   //特殊情况，如示例2不能满足
    if(k<0)
    {
        cout<<0;
        return 0;
    }

    //n行k列 dp[i][j]表示将j分给前i个元素的结果
    vector<vector<int>> dp(n+1,vector<int>(k+1,0));

    //初始化,将0分给任意元素均只有一种分法
    for(int i = 0; i<n; i++)
    {
        dp[i][0]=1;
    }


    //开始dp
    
    //逐渐增加可分配的元素个数
    for(int i = 1; i <= n; i++)
    {
        //逐渐增加可分配的点数
        for(int j = 1; j <= k; j++)
        {
            //再调整当前位置分配的点数即i-1处分配的点数
            for(int kn = 0; kn <= j; kn++)
            {
                //出现相等数剔除
                if(oldArr[i-1] == newArr[i-1]+kn)
                {
                    continue;
                }

                dp[i][j] += dp[i-1][j-kn];

                //为保证不会过大，就每次取个模
                dp[i][j] %= 1000000007;
            
            }

        }
    }

    cout<<dp[n][k];
    
    
    
    return 0;    
}
// 64 位输出请用 printf("%lld")

	
	

		import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int len = scanner.nextInt();
        long[] arrA = new long[len];
        long sum = 0;
        for (int i = 0; i < len; i++) {
            arrA[i] = scanner.nextInt();
            sum += arrA[i];
        }
        long[][] dp = new long[(int) (sum + 1)][len + 1];//求dp[sum][0];
        dp[0][len] = 1;
        for (long m = 1; m <= sum; m++) {
            for (int n = len - 1; n >= 0; n--) {
                long res = 0;
                for (long i = 1; i <= m - len + 1 + n; i++) {
                    if (arrA[n] == i) {
                        continue;
                    }
                    //防止越界，相加之前处理
                    res = (long) (res%(Math.pow(10,9)+7) + dp[(int) (m - i)][n + 1]%(Math.pow(10,9)+7));
                }
                dp[(int) m][n] = res;
            }
        }
        System.out.println(dp[(int) sum][0]);
    }
} 
	

import sys

for i, line in enumerate(sys.stdin):
    if i == 0:
        n = int(line)
    else:
        nums = [int(num) for num in line.split()]

total = sum(nums)
# 创建dp表
dp = [[0] * (total + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, total + 1):
        if i == 1:
            if j != nums[i-1]:
                dp[i][j] = 1
            else:
                dp[i][j] = 0
        else:
            dp[i][j] = (sum(dp[i-1][0:j]) - dp[i-1][j-nums[i-1]]) if (j - nums[i-1]) > 0 else 
            sum(dp[i-1][0:j])


print(dp[n][total] % (10**9+7))

菜狗的简单暴力。 等一个大佬的更强解法。
dp[i][j] 表示在填到第i个数时，总和如果为j的构造方式。
那么i = 0时， 除了j= nums[0]和j= 0. 其他的构造方式都为1.
那么为了方便考虑，就枚举i>0时， 如果当前填写数字[1,sum]会对当前的数组dp[i]造成的影响。
同时考虑到这是个markov过程，所以使用滚动数组优化。
顺便一提，总感觉如果把二维数组表示成在坐标i处，当前和<=j的可行构造数能把复杂度降很多。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    final static int MOD = 1000_000_007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n]; int sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
            sum += nums[i];
        }

        // markov 过程 ， 滚动数组简化空间
        // dp[i][j]: i表示填到第几个, J 表示当前总和。
        int[][] dp = new int[2][sum+1];
        for (int i = 0; i <= sum; i++) dp[0][i] = 1; 
        dp[0][0] = 0; dp[0][nums[0]] = 0;
        for (int i = 1; i < n; i++) {
            int index = i % 2;
            int pre = 1-index;

            for (int kk = 0; kk <= sum; kk++) dp[index][kk] = 0; // 滚动数组清零
            for (int j = 1; j <= sum; j ++) { // 当前填的数字
                if (j == nums[i]) continue; // 不同
                for (int count = j+1; count <= sum; count ++) { // 当前的组合值。
                    int preN = count - j;  // 填
                    dp[index][count] += dp[pre][preN];
                    dp[index][count] %= MOD;
                }
            }
        }

        int index = (n-1)%2;
        System.out.println(dp[index][sum]);
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static final int N = (int)1e9 + 7;
    static int[][] memo;
    static int[] arr;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        arr = new int[n];
        int sum = 0;
        for (int i = 0 ; i < n ; i++) {
            arr[i] = in.nextInt();
            sum += arr[i];
        }
        memo = new int[n][510];
        for (int i = 0 ; i < n ; i++) {
            Arrays.fill(memo[i], -1);
        }
        System.out.println(dfs(0, sum));

    }
    private static int dfs(int cur, int sum) {
        if (sum < 0) return 0;
        if (cur == arr.length) {
            return sum == 0 ? 1 : 0;
        }
        if (memo[cur][sum] != -1) return memo[cur][sum];
        int ans = 0;
        for (int i = 1 ; i <= sum; i++) {
            if (i == arr[cur]) continue;
            ans = (ans + dfs(cur + 1, sum - i)) % N;
        }
        memo[cur][sum] = ans;
        return ans;
    }
}

n = int(input())
nums = list(map(int, input().strip().split()))
s = sum(nums)

mark = 10 ** 9 + 7
# dp[i][j + 1]表示构造长度为j且和为i的数组方式数量
dp = [[0] * (n + 1) for _ in range(s + 1)]
dp[0][0] = 1      # 边界条件

for i in range(1, s + 1):
    for j in range(0, n):
        cnt = 0
        # 当前位置可能的取值。
        # k最小值为1，取最大值时，j前面的元素取值全部为1
        for k in range(1, i - j + 1):
            if k == nums[j]:continue
            cnt = (cnt + dp[i - k][j]) % mark
        dp[i][j + 1] = cnt

print(dp[s][n])

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> a(n);
    int sum = 0;
    for(int& v : a) {
        cin >> v;
        sum += v;
    }

    // 构成 [和为s,前n个元素] 的可能数
    vector<vector<int>> dp(sum+1, vector<int>(n+1, 0));
    dp[0][0] = 1; 

    for (int s=1; s<=sum; s++) {
        for (int l=1; l<=n; l++) {
            int cnt = 0;
            // 前面的和至少为l-1
            for (int ps=l-1; ps<s; ps++) {
                if (s - ps == a[l-1])
                    continue;
                int prev_cnt = dp[ps][l-1];
                cnt = (cnt + prev_cnt) % 1000000007;
            }
            dp[s][l] = cnt;
        }
    }

    cout << dp[sum][n] << endl;

    return 0;
}