易思企业网站管理,seo快速排名软件易下拉霸屏,国外优秀企业网站模板,旅游网站建设需求说明书Problem - 7498 (hdu.edu.cn)
直接dfs显然不行#xff0c;达到了2^500#xff0c;那么我们可以考虑枚举所有红绿灯的状态#xff0c;总共有三种状态#xff0c;k的范围小于等于10#xff0c;因此所有状态数为3^10不会超#xff0c;所以通过三进制状压dp即可完成#xf…Problem - 7498 (hdu.edu.cn)
直接dfs显然不行达到了2^500那么我们可以考虑枚举所有红绿灯的状态总共有三种状态k的范围小于等于10因此所有状态数为3^10不会超所以通过三进制状压dp即可完成这道题目比较卡时间#define int long long 去掉
dp开二维第一维记录前一种状态第二维记录所有红绿灯状态通过mp来判断前一种状态是否存在。
#include bits/stdc.h
using namespace std;
const int inf 0x3f3f3f3f3f3f3f3f;
const int N 2e55;
char a[505][15];
int dp[5][60050];//i有0,1两种状态标记前一种状态是否存在
int mp[5][60050];
int bi[25];
int n,k,mod;void solve(){cinnkmod;int m bi[k];for(int i1;in;i){for(int j0;jk;j){cina[i][j];}}for(int i1;im;i){dp[0][i]0;dp[1][i]0;mp[0][i]0;mp[1][i]0;}dp[0][0] 1;mp[0][0] 1;for(int i1;in;i){for(int jm-1;j0;j--){//三进制枚举所有状态int s j;for(int p0;pk;p){int num s/bi[p];int kk num % 3LL;s - bi[p] * kk;if(a[i][p]-){//反向减去查找前一种状态kk (kk1)%3LL;}else if(a[i][p]){kk (kk2)%3LL;}s bi[p] * kk;}if(mp[(i1)%2][s]||mp[(i1)%2][j])mp[i%2][j] 1;//用或不用dp[i%2][j] (dp[(i1)%2][j] dp[(i1)%2][s]) % mod;}}mapstring,intmpp;for(int i0;im-1;i){string ss;//字符串枚举if(mp[(n%2)][i]0)continue;for(int j0;jk;j){int num i / bi[j];int yu num%3;if(yu 0)ssA;else if(yu 1)ssB;else ss C;}mpp[ss] (dp[(n%2)][i])%mod;}for(auto t:mpp){coutt.first t.second\n;}}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);bi[0] 1;for(int i1;i10;i){bi[i] bi[i-1] * 3LL;}int t1;cint;while(t--){solve();}return 0;
}
