記錄一個菜逼的成長。。
題目連結
題目大意：
有n道題，第i道題放在第j個有價值 Pij
有T組資料。
有n道題，給你一個價值m。
問有多少種方案使得總價值大于等于m。
輸出方案數/總數(分數最簡)
不存在則輸出”No solution”.
如果直接搜的話，時間複雜度是O(n!)的，n<=12顯然會逾時。
考慮dp,考慮狀态壓縮dp。
我一開始想的是dp[i][j] := 表示放了第j道的狀态為i。
然後想狀态轉移，一直卡，後來又想換狀态定義。。然後就gg了。
看了一下網上的定義。突然有種恍然大悟的感覺。。(我tm好菜。。
後話：貌似可以再加一維就可以了，但是第二維就多餘了，就變成下面那樣了。
———以上廢話———-
dp[i][k] := 表示狀态為i,價值和為k的方案數。
比如狀态0100，表示第1道題放的位置是3
狀态0101，表示前面兩道放了位置1和3.此時放了兩道，也就是前兩道，是以下一題是第三道。
狀态轉移方程：
dp[i|(1<<(j−1))][k+a[cnt+1][j]]+=dp[i][k] (cnt表示狀态i放的題目個數)
#include <bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define cl(a,b) memset(a,b,sizeof(a))
#define clr clear()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int maxn = ;
int a[maxn][maxn],n,m,f[maxn];
int dp[<<maxn][];
void init()
{
f[] = ;
for( int i = ; i <= ; i++ ){
f[i] = f[i-] * i;
}
}
int main()
{
init();
int T;scanf("%d",&T);
while(T--){
cl(dp,);
scanf("%d%d",&n,&m);
for( int i = ; i <= n; i++ ){
for( int j = ; j <= n; j++ )
scanf("%d",&a[i][j]);
}
int limit = (<<n);
dp[][] = ;
for( int i = ; i < limit; i++ ){
int cnt = ;
for( int j = ; j < n; j++ ){
if((<<j) & i)cnt++;
}
for( int j = ; j < n; j++ ){
if(!((<<j) & i)){
int t = i | (<<j);
for(int k = ; k <= m; k++ ){
dp[t][min(a[cnt+][j+]+k,m)] += dp[i][k];
}
}
}
}
if(!dp[limit-][m])puts("No solution");
else {
int gcd = __gcd(dp[limit-][m],f[n]);
printf("%d/%d\n",f[n]/gcd,dp[limit-][m]/gcd);
}
}
return ;
}