Spoj, dynamic-programming: ASSIGN - Assignments

August 14, 2016
spoj

有n个学生和n个任务，每个学生有喜欢的任务，输入一个矩阵，第i行第j列表示第i个
学生喜欢第j个任务。把任务分配给所有学生，使得每个学生得到的任务都是他喜欢的。
输出有多少种分配方法。n的最大值是20。

用一个数字的一个位表示这个任务是否已经被分配，如果任务全部被分配，那么这个数字就是(1<<n)-1。可以想到这样的递归方法：solve(i,mask) 表示对i..n这些人分配任务的方法的数目，mask代表此时对1..i-1这些人已经分配了任务，也就是说mask的二进制表示里面有i-1个1。对当前的人，如果他喜欢第j个任务，并且mask的第j位是0，那么就可以把这个任务分配给他，继续考虑下一个人。

/*
 * =====================================================================================
 *
 *       Filename:  main1.cpp
 *
 *    Description:  http://www.spoj.com/problems/ASSIGN/
 *
 *        Version:  2.0
 *        Created:  08/13/2016 14:13:42
 *       Compiler:  g++
 *
 *         Author:  Sabastian (liuxueyang.github.io), read3valprintloop@gmail.com
 *
 * =====================================================================================
 */
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n-1; i >= a; --i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef map<int,int> MI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=1000000007;
const int N=((1<<20)+10);
ll a[25][N];
int b[25][25];
ll result;
int n;
 
ll solve(int stu, ll mask){
  if(a[stu][mask])return a[stu][mask];
  if(stu>=n+1)return a[stu][mask]=1;
  ll result=0;rep(j,0,n){
    if( b[stu-1][j]==1 && !((1<<j)&mask) )
      result+=solve(stu+1,mask|(1<<j));
  }
  return a[stu][mask]=result;
}
 
int main ( void )
{
#ifndef  ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
#endif     /* -----  ONLINE_JUDGE  ----- */
 
  int T;cin>>T;while(T--){
    memset(a,0,sizeof(a)); cin>>n;rep(i,0,n)rep(j,0,n)cin>>b[i][j];
    cout<<solve(1,0)<<endl;
  }
 
  return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

然而，这会TLE。

这个做法递归到最后，递归结束的时候，其实是在solve(stu,mask)里面的stu==n+1的时候。所以我们可以从下到上计算。dp[(1<<n)-1]=1;这是初始的条件。我们把mask从 (1<<n)-2开始循环，一直到0，那么可以发现计算dp[i]的时候dp[i..]已经计算过了。另外，可以根据i里面的1的个数来判断当前是哪一个学生。

复杂度是O(n*2^n)

/*
 * =====================================================================================
 *
 *       Filename:  main1.cpp
 *
 *    Description:  http://www.spoj.com/problems/ASSIGN/
 *
 *        Version:  2.0
 *        Created:  2016年08月14日 13时32分54秒
 *       Compiler:  g++
 *
 *         Author:  Sabastian (liuxueyang.github.io), read3valprintloop@gmail.com
 *
 * =====================================================================================
 */
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n-1; i >= a; --i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef map<int,int> MI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=1000000007;
const ll N=1<<20;
int b[25][N];
ll a[N];
int n;
int cnt1(ll n){int cnt=0;while(n){if(n&1) ++cnt;n/=2;}return cnt;}

int main ( void )
{
#ifndef  ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
#endif     /* -----  ONLINE_JUDGE  ----- */

    int T;cin>>T;while(T--) {
        cin>>n; rep(i,1,n+1) rep(j,1,n+1) cin>>b[i][j];
        memset(a,0,sizeof(a));
        a[(1<<n)-1]=1;
        per(mask,0,(1<<n)-1){int row=cnt1(mask);row++;
            rep(j,1,n+1) if(b[row][j]&&(0==(mask&(1<<(j-1))))) a[mask]+=a[mask|(1<<(j-1))];
        }
        cout<<a[0]<<endl;
    }

  return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

Read more