HDU多校-交通管控

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 = 2e5+5;
char a[505][15];
int dp[5][60050];//i有0,1两种状态，标记前一种状态是否存在
int mp[5][60050];
int bi[25];
int n,k,mod;void solve(){cin>>n>>k>>mod;int m = bi[k];for(int i=1;i<=n;i++){for(int j=0;j<k;j++){cin>>a[i][j];}}for(int i=1;i<=m;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 i=1;i<=n;i++){for(int j=m-1;j>=0;j--){//三进制枚举所有状态int s = j;for(int p=0;p<k;p++){int num = s/bi[p];int kk = num % 3LL;s -= bi[p] * kk;if(a[i][p]=='-'){//反向减去，查找前一种状态kk = (kk+1)%3LL;}else if(a[i][p]=='+'){kk = (kk+2)%3LL;}s += bi[p] * kk;}if(mp[(i+1)%2][s]||mp[(i+1)%2][j])mp[i%2][j] = 1;//用或不用dp[i%2][j] = (dp[(i+1)%2][j] + dp[(i+1)%2][s]) % mod;}}map<string,int>mpp;for(int i=0;i<=m-1;i++){string ss;//字符串枚举if(mp[(n%2)][i]==0)continue;for(int j=0;j<k;j++){int num = i / bi[j];int yu = num%3;if(yu == 0)ss+='A';else if(yu == 1)ss+='B';else ss += 'C';}mpp[ss] = (dp[(n%2)][i])%mod;}for(auto &t:mpp){cout<<t.first<<" "<<t.second<<"\n";}}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);bi[0] = 1;for(int i=1;i<=10;i++){bi[i] = bi[i-1] * 3LL;}int t=1;cin>>t;while(t--){solve();}return 0;
}