题目链接:点击进入 开始看到m和k都很小,就直接暴力了一发,结果T了.后面看到m只有6那么大,k又小于10,就觉得可以用记忆化搜索,状态我们就定为dp[n1][n2][n3][n4][n5][n6],表示n1–n6六种化学试剂的量,状态转移就时选两份试剂进行混合.
代码如下:
;maxn=12;int dp[maxn][maxn][maxn][maxn][maxn][maxn];int vis[maxn][maxn][maxn][maxn][maxn][maxn];typedef struct{int x,hot;}P;P p[10][10];int a[20],ans;int dfs(int a,int b,int c,int d,int e,int f,int n){if(n==1) return 0;int& res=dp[a][b][c][d][e][f];int& flag=vis[a][b][c][d][e][f];if(flag) return res;int num[7]={0,a,b,c,d,e,f};int tmp=INF;for(int i=1;i<=6;i++)for(int j=1;j<=6;j++){if(i==j&&num[i]<2) continue;if(num[i]==0||num[j]==0) continue;num[i]–; num[j]–; num[p[i][j].x]++;tmp=min(tmp,dfs(num[1],num[2],num[3],num[4],num[5],num[6],n-1)+p[i][j].hot);num[i]++;num[j]++;num[p[i][j].x]–;}flag=1; res=tmp;return tmp;}int main(){// freopen(“in.txt”,”r”,stdin);int t,m,k,num[7];char str[10];scanf(“%d”,&t);for(int T=1;T<=t;T++){if(T!=1)scanf(“%s”,str);scanf(“%d”,&m);for(int i=1;i<=m;i++)for(int j=1;j<=m;j++){scanf(“%d%d”,&p[i][j].x,&p[i][j].hot);}scanf(“%d”,&k);memset(vis,0,sizeof(vis));memset(num,0,sizeof(num));for(int i=1;i<=k;i++){int x;scanf(“%d”,&x);num[x]++;}dfs(num[1],num[2],num[3],num[4],num[5],num[6],k);printf(“%d\n”,dp[num[1]][num[2]][num[3]][num[4]][num[5]][num[6]]);}scanf(“%s”,str); return 0;}
，与其临渊羡鱼，不如退而结网。
