11

这是一个算法问题，我有解决方案，但它有性能问题。

问题描述

有 n 个变量和 m 个要求。需求表示为 (x <= y)，这意味着第 x 个变量必须小于或等于第 y 个变量。为每个变量分配小于 10 的非负数。请计算符合所有要求的不同作业的数量。当且仅当在这两个赋值中为至少一个变量分配了不同的数字时，两个赋值是不同的。将答案模数为 1007。

输入格式：

输入的第一行包含两个整数 n 和 m。然后是 m 行，每行包含 2 个空格分隔的整数 x 和 y，这意味着一个要求 (x <= y)。

输出格式：

在一行中输出答案。

约束：

0 < n < 14

0 < 米 < 200

0 <= x, y < n

样本输入：

6 7

1 3

0 1

2 4

0 4

2 5

3 4

0 2

样本输出：

1000

下面是我的解决方案。当 n=13 和 m=199 时，需要很长时间才能得到结果，但可接受的时间是 5 秒。

那么有人能想出更好的方法来进一步优化吗？谢谢你。

我目前的解决方案：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication81
{
    class Program
    {
        const int N = 10;
        static List<Condition> condition = new List<Condition>();
        static void Main(string[] args)
        {
            string[] line1 = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            int n = int.Parse(line1[0]);
            int m = int.Parse(line1[1]);

            for (int i = 0; i < m; i++)
            {
                string[] line = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                condition.Add(new Condition()
                {
                    X = int.Parse(line[0]),
                    Y = int.Parse(line[1])
                });
            }

            //
            List<int[]> rlist = new List<int[]>();

            for (int j = 0; j < N; j++)
            {
                int[] assignments = new int[n];
                for (int i = 0; i < n; i++)
                    assignments[i] = -1;
                assignments[0] = j;
                rlist.Add(assignments);
            }
            for (int j = 1; j < n; j++)
            {
                List<int[]> rlist2 = new List<int[]>(rlist.Count*5);
                for (int k = 0; k < rlist.Count; k++)
                {
                    for (int l = 0; l < N; l++)
                    {
                        rlist[k][j] = l;
                        if (CanPassCondition(rlist[k]))
                            rlist2.Add((int[])rlist[k].Clone());
                    }
                }
                rlist = rlist2;
            }

            Console.Write(rlist.Count % 1007);
        }


        private static bool CanPassCondition(int[] p)
        {
            foreach (var c in condition)
            {
                if (p[c.X] == -1 || p[c.Y] == -1)
                    continue;

                if (p[c.X] > p[c.Y])
                    return false;
            }
            return true;
        }
    }

    class Condition
    {
        public int X;
        public int Y;

        public override string ToString()
        {
            return string.Format("x:{0}, y:{1}", X, Y);
        }
    }
}
4

1 回答 1

3

这是 Java 中的一个解决方案，即使在 n=13、m=199 的情况下，它对我来说也能很快工作：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Assignments
{
    private static Map <String, Long> solutions = new HashMap <String, Long> ();

    private static boolean [][] constraints;

    private static long solve (int n, int [] low, int [] high)
    {
        StringBuilder sb = new StringBuilder ();

        for (int i = 0; i < n; i++)
        {
            sb.append (low [i]);
            sb.append (high [i]);
        }

        String signature = sb.toString ();

        Long result = solutions.get (signature);
        if (result == null)
        {
            result = Long.valueOf (doSolve (n, low, high));
            solutions.put (signature, result);
        }

        return result.longValue ();
    }

    private static long doSolve (int n, int [] low, int [] high)
    {
        if (n == 0) return 1;
        else
        {
            long result = 0;

            for (int i = low [n - 1]; i <= high [n - 1]; i++)
            {
                int [] l = new int [n - 1];
                int [] h = new int [n - 1];

                for (int j = 0; j < n - 1; j++)
                {
                    l [j] = constraints [n - 1][j] ? Math.max (low [j], i) : low [j];
                    h [j] = constraints [j][n - 1] ? Math.min (high [j], i) : high [j];
                }

                result += solve (n - 1, l, h);
            }

            return result;
        }
    }

    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = 
            new BufferedReader (
                new InputStreamReader(System.in));

        String nm = reader.readLine ();
        String [] pair = nm.split(" ");
        int n = Integer.parseInt(pair [0]);
        int m = Integer.parseInt(pair [1]);

        constraints = new boolean [n][];
        for (int i = 0; i < n; i++)
            constraints [i] = new boolean [n];

        int [] low = new int [n];
        int [] high = new int [n];
        for (int i = 0; i < n; i++)
            high [i] = 9;

        for (int i = 0; i < m; i++)
        {
            String ab = reader.readLine();
            pair = ab.split (" ");
            int a = Integer.parseInt(pair [0]);
            int b = Integer.parseInt(pair [1]);
            constraints [a][b] = true;
        }

        System.out.println(solve (n, low, high));
    }
}

实际上，一旦你有 13 个变量，你可能只有 156 (13 * 12) 个有意义的约束，但是。

样本输入：

13 1
3 8

输出：

5500000000000

另一个示例输入：

13 12
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12

输出：

497420
于 2013-02-19T07:01:47.237 回答