当前位置: 首页 > 工具软件 > reaction > 使用案例 >

uva 10604 Chemical Reaction

酆华皓
2023-12-01
题意:有t组测试数据。
每组测试数据开始有一个整数n,表示有n种试剂(最多6种)。接下来的n*n行列出来了每种试剂混合产生的化合物以及放出的热量。
然后一个整数m,代表有m个试管(最多10个)。
接下来一行有m个数,表示m个试管里分别装了哪几种试剂。

问怎么组合能产生最少的热量。测试样例之间用/分开,结果用.表示

定义了六维的状态直接跑。。。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 1<<30
const int N=12;
bool vis[N][N][N][N][N][N];
int tube[N],data[N][N][2],map[N][N][N][N][N][N];
int dp(int,int,int,int,int,int);
int main()
{
    //freopen("10604","r",stdin);
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        memset(vis,0,sizeof(vis));
        memset(map,0,sizeof(map));
        memset(tube,0,sizeof(tube));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d%d",&data[i][j][0],&data[i][j][1]);
            }
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            int temp;
           scanf("%d",&temp);
           tube[temp]++;
        }
        printf("%d\n",dp(tube[1],tube[2],tube[3],tube[4],tube[5],tube[6]));
        char use[5];scanf("%s",use);
    }
    return 0;
}
int dp(int a,int b,int c,int d,int e,int f)
{
    bool &flag=vis[a][b][c][d][e][f];
    int &res=map[a][b][c][d][e][f];
    if(flag) return res;
    else
    {
        res=INF;
        int m[7]={0,a,b,c,d,e,f};
        for(int i=1;i<=6;i++)
        {
            for(int j=1;j<=6;j++)
            {
                if(i==j&&m[i]<2) continue;
                if(m[i]&&m[j])
                {
                    m[i]--;m[j]--;m[data[i][j][0]]++;
                    int temp=dp(m[1],m[2],m[3],m[4],m[5],m[6]);
                    if(temp!=INF) res=min(res,temp+data[i][j][1]);
                    m[i]++;m[j]++;m[data[i][j][0]]--;

                }
            }
        }
        flag=1;
        if(res==INF) res=0;
        return res;
    }
}


 类似资料:

相关阅读

相关文章

相关问答