最近做的矩阵选数问题比较多，写一篇博客。

1.每个人戴不同帽子的方案数.

https://leetcode-cn.com/problems/number-of-ways-to-wear-different-hats-to-each-other/

题目大意:有n个人40顶帽子，每个人喜欢不同的帽子,求满足每人拿到喜欢帽子的方案数.(n<=10 )
分析：看数据范围就是可以二进制暴力枚举,dp[i][j]表示前i顶帽子分分配方案为j ( j---二进制下 k位置为1 表示第k个人拿到喜欢的帽子 ) 的方案数.那么转移方程就是:

class Solution {
public:

    const int maxn=2049;
    const int mod=1e9+7;
    bool vis[50][50];
    int dp[50][2049];

    void inc( int &x,long long y ) { x=(x+y)%mod; } 

    int numberWays(vector<vector<int>>& hats) {
        int n=hats.size();
        memset(vis,0,sizeof(vis));
        for( int i=0;i<n;i++ )
        {
            for( int v:hats[i] ) vis[v][i]=true;
        }
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for( int i=1;i<=40;i++ )
        {
            for( int j=0;j<(1<<n);j++ )
            {
                inc(dp[i][j],dp[i-1][j]);
                for( int k=0;k<n;k++ )
                {
                    if( ( j>>k & 1  ) && vis[i][k] )
                    inc(dp[i][j],dp[i-1][j^(1<<k)]);
                }
            }
        }
        return dp[40][(1<<n)-1];
    }
};

2. 有序矩阵中的第 k 个最小数组和

题目大意：n * m的矩阵每行选择一个数形成一个数组，求所有可能数组中的第k个最小数组和.( 1<=n,m<=40,k<=min(200,n*m) )
分析:
比赛时候写了背包 结果方案数爆longlong 自闭
---当然现在我还是认为背包可以写 怀疑测评机太捞不让过!!!
正解: 二分check.我们先处理出数组和的最小值和数组和的最大值作为二分的左右边界，然后二分进行的dfs check判断数组和小于等于mid的数组个数.

class Solution {
public:
    vector <vector<int>> temp;
    int m,n;

    int kthSmallest( vector<vector<int>>& mat, int k )  
    {
        temp=mat;
        m=mat.size(),n=mat[0].size();
        int left=0,right=0;
        for(int i=0;i<m;i++) left+=mat[i][0],right+=mat[i].back();
        int init=left;
        while( left<right )
        {
            int mid=(left+right)>>1;
            int num=1;
            dfs(mid,0,init,num,k);
            if(num>=k) right=mid;
            else left=mid+1;
        }
        return left;
    }
    void dfs( int mid,int index,int sum,int& num,int k )
    {
        if (sum>mid || index==m || num>k ) return;
        dfs(mid,index+1,sum,num,k);
        for( int i=1;i<n;i++ )
        {
            if( sum+temp[index][i]-temp[index][0]<=mid )
            {
                num++;
                dfs(mid,index+1,sum+temp[index][i]-temp[index][0],num,k);
            }
            else  break;

        }
    }
};

dp的方法 不过超时了....不清楚为啥

class Solution {
public:
    #define N 200005
    int a[42][42];
    int dp[42][N],len[42];
    int mins[42],maxs[42];

    int kthSmallest(vector<vector<int>>& mat, int k) {

        int n=mat.size();

        for( int i=1;i<=n;i++ )
        {
            len[i]=mat[i-1].size();
            for( int j=1;j<=len[i];j++ ) a[i][j]=mat[i-1][j-1];
        } 

        mins[0]=maxs[0]=0;
        for( int i=1;i<=n;i++ ) 
        {
            mins[i]=mins[i-1]+a[i][1];
            maxs[i]=maxs[i-1]+a[i][len[i]];
        }
        dp[0][0]=1;
        for( int i=1;i<=n;i++ )
        {
            for( int v=maxs[i];v>=mins[i];v-- )
            {
                for( int j=1;j<=len[i];j++ )
                {
                    if( v<a[i][j] ) continue;
                    dp[i][v]=min(k,dp[i][v]+dp[i-1][v-a[i][j]]);
                }
            }
        }
        int ans=0;
        for( int i=mins[n];i<=maxs[n];i++ )
        {

            if( dp[n][i]<=0 ) continue;
            if( k>=dp[n][i] )
            {
    //            ans+=dp[n][i]*i;
                k-=dp[n][i];
                if( k==0 ) 
                {
                    ans=i;
                    break;
                }
            }
            else
            {
                ans=i;
                break;
            }
        }
        return ans;
    }
};

3.三角形

那么这道题来解释一下我为什么上道题会去写背包

题目大意:n个箱子，箱子里面有很多宝物，每个宝物可以换 的钱,现在每个箱子选择一个宝物，选择n个宝物的价值总和就是选择方案的值,求前k小方案价值总和.(n,m<=100,k<=1000)
分析:这题先讲dp的方法. 表示前i行的选数方案的值为j,考虑转移方程:

表示前i行选数方案的最大值
表示前i行选数方案的最小值.

• 有个要注意的地方,方案数可能会爆long long ,那么我们在转移方程中加一个
  
• 最后我们计算答案 直接遍历 找到第k小值即可.

#include<bits/stdc++.h>
using namespace std;

const int maxn=105;

int dp[maxn][maxn*maxn],a[maxn][maxn];
int len[maxn];
int maxs[maxn],mins[maxn];
inline int read()
{
    int f=1,x=0;char s=getchar();
    for( ;isdigit(s);x=x*10+s-48,s=getchar() );
    return x;
}

int main()
{
    int n=read(),k=read();
    for( int i=1;i<=n;i++ )
    {
        len[i]=read();
        for( int j=1;j<=len[i];j++ ) a[i][j]=read();
    } 
    dp[0][0]=1;
    mins[0]=maxs[0]=0;
    for( int i=1;i<=n;i++ ) 
    {
        for( int j=1;j<=len[i];j++ )
        {
            mins[i]=min(mins[i-1]+a[i][j],mins[i]);
            maxs[i]=max(maxs[i-1]+a[i][j],maxs[i]);
        }
    }

    for( int i=1;i<=n;i++ )
    {
        for( int v=maxs[i];v>=mins[i];v-- )
        {
            for( int j=1;j<=len[i];j++ )
            {
                if( v<a[i][j] ) continue;
                dp[i][v]=min(k,dp[i-1][v-a[i][j]]+dp[i][v]);
            }
        }
    }
    int ans=0;
    for( int i=mins[n];i<=maxs[n];i++ )
    {
        if( !dp[n][i] ) continue;
        if( k>=dp[n][i] )
        {
            ans+=dp[n][i]*i;
            k-=dp[n][i];
        }
        else
        {
            ans+=k*i;
            break;
        }
    }
    printf("%d\n",ans);
}