瑞安网站建设优化推广,网站开发技术考试试卷,易企秀h5制作免费,中国建设人才网官网证书查询题目阐述#xff1a; 给定n个座位#xff0c;n个人#xff0c;每个人可以做n个位置中的任意一个#xff0c;P[i][j]代表第i个人做第j个位置获得的分数#xff0c;求有多少种排列方式使得获得的分数大于等于M。 这道题跟数位dp的思想很像#xff0c;都是穷举可能的方式 给定n个座位n个人每个人可以做n个位置中的任意一个P[i][j]代表第i个人做第j个位置获得的分数求有多少种排列方式使得获得的分数大于等于M。 这道题跟数位dp的思想很像都是穷举可能的方式不过数位DP由于前缀的影响可以记忆化这道题由于n较小可以直接状态压缩. 定义状态d[i][s][t]代表已经放了i个座位放的人数集合为s获得分数为t的排列的数量。 然后每次暴力枚举每个位置可能会放的人 d[i][s | (1 j)][t p[j][i]] d[i-1] [s] [t]; 重点是如何实现 #include iostream
#include cstdio
#include cstring
#include cstdlib
#define maxn 13
using namespace std;
int d[1(maxn)][505]; //表示到达状态s时产生的最大能量
int n,m;
int P[maxn][maxn];
int ans;
void init()
{ans0;memset(d,0,sizeof(d));
}
//GCD
//求最大公约数
//O(logn)
int gcd(int a, int b)
{if (b 0)return a;elsereturn gcd(b, a%b);
}
int isok(int i)
{int t0;while(i){if(i1) t;i1;}return t;
}
void solve()
{int tot(1n)-1;d[0][0]1; //其实可以理解成d[-1][0][0]否则下面就需要特殊处理i等于0for(int i0;in;i) //代表第i个位置{for(int s0;stot;s) //遍历所有状态{if(isok(s)!i) continue ;//检测哪些是前i-1个位置的状态for(int t0;tm;t) //遍历所有获得的分数{if(!d[s][t]) continue; //检测哪些是前i-1个位置获得的分数for(int j0;jn;j) //枚举第i个位置可能放的人{if( s (1j) ) //检测前i-1个位置是否放过continue;int state s | (1j);int MMmin(m,tP[j][i]);d[state][MM]d[s][t];}}}}ansd[tot][m];
}int main()
{// freopen(test.txt,r,stdin);int fac[maxn];fac[0]1;for(int i1;imaxn;i)fac[i]fac[i-1]*i;int t;scanf(%d,t);while(t--){scanf(%d%d,n,m);init();for(int i0;in;i)for(int j0;jn;j){scanf(%d,P[i][j]);}solve();int d gcd(fac[n], ans);if (ans 0)printf(No solution\n);elseprintf(%d/%d\n, fac[n]/d, ans/d);}return 0;
} bfs实现 #include iostream
#include cstdio
#include cstring
#include cstdlib
#include queue
#define maxn 13
using namespace std;
int d[1(maxn)][505]; //表示到达状态s时产生的最大能量
int n,m;
int P[maxn][maxn];
int ans;
int gcd(int a, int b)
{if (b 0)return a;elsereturn gcd(b, a%b);
}int bit(int i)
{int t0;while(i){if(i1) t;i1;}return t;
}
struct node
{int s,t,cnt0;
};
int visit[1maxn][505];
void bfs()
{queue node que;memset(visit,0,sizeof(visit));int tot(1n)-1;node start,last;start.s0; start.t0;start.cnt0;que.push(start);visit[start.s][start.t]1;d[0][0]1;while(!que.empty()){node curque.front();que.pop();for(int i0;in;i){if(cur.s (1i))continue;node next ;next.s cur.s | (1i);next.cntcur.cnt1;next.t min(m,cur.tP[i][cur.cnt]); //将第i个人放在当前位置然后才会加1d[next.s][next.t] d[cur.s][cur.t];if(visit[next.s][next.t]) //保证只进队一次continue;que.push(next);visit[next.s][next.t]1;}}ansd[tot][m];
}int main()
{// freopen(test.txt,r,stdin);int fac[maxn];fac[0]1;for(int i1;imaxn;i)fac[i]fac[i-1]*i;int t;scanf(%d,t);while(t--){scanf(%d%d,n,m);ans0;memset(d,0,sizeof(d));;for(int i0;in;i)for(int j0;jn;j){scanf(%d,P[i][j]);}bfs();int d gcd(fac[n], ans);if (ans 0)printf(No solution\n);elseprintf(%d/%d\n, fac[n]/d, ans/d);}return 0;
} 转载于:https://www.cnblogs.com/xianbin7/p/4780565.html
