烟台做网站工资,青岛海西建设集团官方网站,外贸网站建设规划,公司的oa是什么意思UVA_10604 一开始看错题了#xff0c;以为化学物质最多会有10个#xff0c;所以定义不了10维的去跑#xff0c;便用了类似状态压缩的方式#xff0c;把化学物质的状态压缩成一个整数#xff0c;然后用哈希表建立一个索引#xff0c;再用记忆化搜素去处理就可以了。 之所以…UVA_10604 一开始看错题了以为化学物质最多会有10个所以定义不了10维的去跑便用了类似状态压缩的方式把化学物质的状态压缩成一个整数然后用哈希表建立一个索引再用记忆化搜素去处理就可以了。 之所以能这么做关键在于总状态并不是很多我们可以粗略的估算一下即便有10种药品时状态最多有(10^10)/10!考虑到混合之后达到的状态最多再乘个10而已用计算器算一下数值还是比较小的。 当然这个题目可以用6维的数组去跑但如果药品数多了之后n维的f显然空间是开不下的但总状态数却不是很多所以哈希表虽然写着复杂但多少有些适用范围的优势。 此外要注意到这个题目A和B混合与B和A混合有可能是不一样的所以我们在枚举决策的时候要注意一下。 #includestdio.h#includestring.h#define MAXN 10#define HASH 1000003#define MAXD 50000#define INF 0x3f3f3f3fint N, K, e, head[HASH], next[MAXD], st[MAXD][6], g[MAXN][MAXN], heat[MAXN][MAXN], f[MAXD];int hash(int p[]){int i, v 0;for(i 0; i 6; i ) v v * 10 p[i];return (v 0x7fffffff) % HASH;}void insert(int s){int h hash(st[s]); next[e] head[h]; head[h] e; e ;}int check(int s){int i;int h hash(st[s]);for(i head[h]; i ! -1; i next[i])if(memcmp(st[i], st[s], sizeof(st[i])) 0)break;return i;}void init(){int i, j, k, t; scanf(%d, N);for(i 0; i N; i )for(j 0; j N; j ) { scanf(%d%d, k, t); k --; g[i][j] k; heat[i][j] t; }}int dp(int cur){int i, j, k, t, min INF; k check(cur);if(k 0)return f[k]; insert(cur);for(i 0; i 6; i )if(st[cur][i])for(j 0; j 6; j )if(st[cur][j]) {if(j i st[cur][j] 2)continue; memcpy(st[e], st[cur], sizeof(st[e])); st[e][i] --, st[e][j] --, st[e][g[i][j]] ; t dp(e);if(t heat[i][j] min) min t heat[i][j]; }if(min INF) min 0;return f[cur] min;}void solve(){int i, j, k, res; memset(head, -1, sizeof(head)); memset(st[0], 0, sizeof(st[0])); scanf(%d, K);for(i 0; i K; i ) { scanf(%d, k); k --; st[0][k] ; } e 0; memset(f, 0x3f, sizeof(f)); res dp(e); printf(%d\n, res);}int main(){int t;char b[5]; scanf(%d, t);while(t --) { init(); solve(); scanf(%s, b); }return 0;} 转载于:https://www.cnblogs.com/staginner/archive/2011/12/06/2277838.html
