涂色II

动态规划

• 状态表示:f[i][j]表示考虑前i个物体, 并将i个物体染成j这种颜色的不同方案数
• 状态计算: 枚举i - 1位置可以染的所有的颜色, 若颜色k后可以接j, 则f[i][j] += f[i - 1][k]
• 最终答案: 枚举i从1 - m,ans += f[n][i]

时间复杂度

• 状态是O(nm)
• 转移是O(m)
• 整体时间复杂度为O(nm^2)

// 提交时间：2021-10-18 语言：C++ 运行时间： 27 ms 占用内存：508K 状态：答案正确 #include <bits/stdc++.h>

using namespace std;
const int N = 1010, M = 12, MOD = 1e9 + 7;
int f[N][M];
int nxt[M][M];

void solve(){
    memset(nxt, 0, sizeof(nxt));
    memset(f, 0, sizeof(f));
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 1; i <= m; i ++ )
        for (int j = 1; j <= k; j ++ ) {
            int x; 
            cin >> x ;
            nxt[i][x] = 1;
        }

    for (int i = 1; i <= m; i ++ )
        f[1][i] = 1;    
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            for (int k = 1; k <= m; k ++ )
                if (nxt[k][j] == 0)
                    f[i][j] = (f[i][j] + f[i - 1][k]) % MOD;
        }
    int ans = 0;
    for (int i = 1; i <= m; i ++ )
        ans = (ans + f[n][i]) % MOD;
    ans = (ans + MOD) % MOD;
    cout << ans << '\n';
}

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

    // 贝壳2021开发岗 第四题

    static long modd = 0;

    public static void main(String[] args) {

        modd = (long) Math.pow(10, 9);
        modd += 7;
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            int t = sc.nextInt();

            for (int l = 0; l<=t-1; l++) {
                int n = sc.nextInt();
                int m = sc.nextInt();
                int k = sc.nextInt();

                int[][] notFollow = new int[m+1][k];
                long[][] res = new long[m+1][n+1];

                for (int i = 1; i<=m; i++) {
                    for (int j = 0; j<=k-1;j++) {
                        notFollow[i][j] = sc.nextInt();
                    }
                    Arrays.sort(notFollow[i]);
                }

                long finalRes = 0;
                for (int i = 1; i<=n;i++) {
                    if (i == 1) {
                        for (int j = 1; j<=m; j++) {
                            res[j][i] = 1;
                        }
                    } else {
                        for (int j = 1; j<=m; j++) {
                            HashSet<Integer> hs = new HashSet<>();
                            for (int s = 1; s<=m; s++) {
                                hs.add(s);
                            }
                            for (int h = 0; h<=k-1; h++) {
                                hs.remove(notFollow[j][h]);
                            }
                            long sum = 0;
                            for (Integer follow: hs
                                 ) {
                                sum = (sum + (res[follow][i-1] % modd) % modd);
                            }
                            if (i == n) {
                                finalRes = (sum + finalRes) % modd;
                            }
                            res[j][i] = sum;
                        }
                    }
                }

                System.out.println(finalRes % modd);
            }
        }
    }
}