粉刷

题目

题目描述
新街口有许许多多的建筑，现在需要给一些建筑重新涂色，使得新街口更加得美丽。
现在新街口一共有N座建筑物，有M种颜色的漆料可以用来涂色，根据美学关系，有些时候，两种特定颜色的建筑数目之间差值为奇数或者偶数的情况下，会增加整体的可观赏程度，为了简化问题，我们将所有的建筑物都视为是完全一样的，不考虑任何的外界环境因素，则，一共有M-1种颜色的两两组合使其差值为奇数或偶数，问你一共有多少种涂色方案。

解答要求
时间限制：1000ms, 内存限制：100MB
输入
输入数据的第一行输入两个整数N, M(1 <= N <= 500, 1 <= M <= 100)。
下面M-1行，每行3个正整数a,b,v(1 <= a, b <= M, v ∈ {0, 1})。
表示第a种和第b种颜色之间数目的差值为奇数还是偶数，0表示奇数，1表示偶数。

输出
输出所有的涂色方案的数目MOD 1000000007的值。

下面的讲述基于如下样例

4 3
1 2 0
1 3 1

可以将题目转化为

一个数 N 分成 M 个的数
使得 N = a[0] + a[1] + a[2] + … + a[M-1]
现对 a[i] 的奇偶性进行限制
问有多少种分法

其中a[i]的奇偶性可以通过给出的M-1条规则限定，于是我们先确定a[i]在满足奇偶性的前提下最少应该粉刷掉几个房子，以下面两条规则为例

1 2 1
2 3 1

我们可以推断出

1 3 0

全部的奇偶性可以分为两种
1 0 1和0 1 0

在1 0 1的情况下，4个房子已经粉刷掉2个了，剩下2个房子要分配给3种颜色，可以为0，其中每种颜色粉刷的房子是2的倍数，最终的结果为三种

2 0 0
0 2 0
0 0 2

因此总的方案为3种，另外的0 1 0之后，屋子只剩下3个，所以得到的方案为0。

将题目理解为一个数 n 分为 m 个数： N = a[0] + a[1] + a[2] + … + a[m-1]
1.确定M个数的奇偶性，用1表示奇数，0表示偶数
    方法：先令一个位置为偶数，其余位置奇偶性根据输入条件计算，奇数和记为sum
2.剩余分配数count = n - sum；因为以2为单位来分配给任意位置，不会改变原奇偶性。
    故若count % 2 != 0，则需调换第一步确定的奇偶性，0变1,1变0
3.结果就变成：
    将count分解为m个数（可以为0），有多少种分法？
就变成了典型的动态规划

我的代码：

package com.company;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class painting {
    public static void main(String[] args) {
//        System.out.println(dp(1, 3));

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt();

        if(M == 1)
            System.out.println(1);

        Queue<Integer[]> queue = new LinkedList<>();
        for (int i = 0; i < (M - 1); i++) {
            int a = sc.nextInt(), b = sc.nextInt(), r = sc.nextInt();
            queue.add(new Integer[]{a, b, r});
        }

        Integer[][] evensAndOdds = CalcColorPriority(M, queue);

        int results = 0;
        for (Integer[] states : evensAndOdds) {
            int sum = 0;
            for (int i = 1; i <= M; i++) {
                sum += states[i];
            }
            int left = N - sum;

            if(left % 2 == 0) {
                // 还有left个房子没有染色，M个颜色，每个颜色染2个房子
                // 等效于：M个颜色染left/2个房子
                // 等效于：袋子重量为left/2，有M个无限的物品
                results = (results + dp(left/2, M)) % 1000000007;
            }
        }

        System.out.println(results);
    }

    public static Integer[][] CalcColorPriority(int M, Queue<Integer[]> queue) {
        Integer[] evens = new Integer[M+1];
        Integer[] odds = new Integer[M+1];

        Integer[] abr = queue.poll();
        int a = abr[0], b = abr[1], r = abr[2];
        evens[a] = 0;
        evens[b] = evens[a] ^ r;

        while(!queue.isEmpty()) {
            abr = queue.poll();
            a = abr[0]; b = abr[1]; r = abr[2];

            if(evens[a]==null && evens[b]==null) {
                queue.add(abr);
            }else{
                if(evens[a] != null) {
                    evens[b] = evens[a] ^ r;
                }else{
                    evens[a] = evens[b] ^ r;
                }
            }
        }

        for (int i = 1; i <= M; i++) {
            odds[i] = 1 - evens[i];
        }

        return new Integer[][]{evens, odds};
    }

    public static int dp(int capacity, int numOfThings) {
        int[][] dp = new int[numOfThings+1][capacity + 1];

        for (int i = 0; i <= capacity; i++) {
            dp[0][i] = Integer.MIN_VALUE;
        }

        for (int i = 0; i <= numOfThings; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= numOfThings; i++) {
            for (int j = 1; j <= capacity; j++) {
                int a = (dp[i][j-1] == Integer.MIN_VALUE ? 0 : dp[i][j-1]);
                int b = (dp[i-1][j] == Integer.MIN_VALUE ? 0 : dp[i-1][j]);
                dp[i][j] = (a + b) % 1000000007;
            }
        }

        return dp[numOfThings][capacity];
    }
}