weapon制作武器 (weapon.pas/c/cpp) 解题报告
制作武器weapon.pas/c/cpp) 背景
WZland的紧急避难所很快就建好了，WZland的居民们陆续地来到这个紧急避难所。但
WZland的许多居民不肯躲避，他们想要和外星人正面作战……
问题描述
在紧急避难所内，应广大居民的要求，WZland的国王决定成立一个自卫队，自卫队由
WZOI的JHB来担任领导。
JHB成为自卫队的领导之后，他的首要任务就是制作武器。WZland盛产矿石，每一种矿
石中都含有巨大的能量。当两块矿石相结合，会有一块消失而另一块保留下来，并且会产生
巨大能量。JHB想通过吸收这些能量，制造出一种能量化的武器，这个武器的杀伤力就是产
生的能量总和。
JHB找人弄到了若干块不同的矿石（每种矿石有且只有一种），他想用这些矿石制作出杀
伤力最大的武器。他把这些矿石交给WZOI的你，然后你需要制作出他需要的武器。当然一
个武器是不够的，JHB陆续给你送来了若干组矿石，你需要将每组的矿石都制作成武器。
输入格式
输入数据第一行包含一个整数T，表示有T组矿石；
对于每组矿石会有若干行来描述。
第一行包含一个整数N，表示当前组矿石的种类。
接下来N行每行N个整数，第i行的第j个数表示矿石i和矿石j结合，然后j消失i留下产生的能
量。
输出格式
输出数据有T行，每行一个整数S，分别表示矿石造出来的武器的最大杀伤力。
样例输入输出
Sample #1
weapon.in weapon.out
1 16
3
0 10 1
11 0 3
4 5 0
Sample #2
weapon.in weapon.out
2 4
2 22
0 4
1 0
3
0 20 1
12 0 1
1 10 0
样例解释
对于Sample #2 的第二个测试点，我们可以这样制作武器：1 和2 合并留下2，获得能量
12，3 和2 合并留下3，获得能量 10，总能量为22。
数据规模
对于30 的数据，2≤N≤10，T≤10；
对于50 的数据，2≤N≤10，T≤100；
对于100 的数据，2≤N≤10，T≤500；
对于100 的数据，保证S≤Maxlongint。
时间限制
1s
刷表大法好，状压大法好。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;
int t , n , links[][] , f[] ; void Init( )
{
scanf( "%d" , &n ) ;
for( int x = ; x <= n ; ++x )
for( int y = ; y <= n ; ++y )
scanf( "%d" , &links[x][y] ) ;
} void Solve( )
{
memset( f , , sizeof(f) ) ;
int ans = ;
for( int k = ; k <= ( << n ) - ; ++k )
for( int i = ; i <= n ; ++i )
for( int j = ; j <= n ; ++j )
{
if( i == j || ( k & ( <<( i - ) ) ) || ( k & ( << (j-) ) ) ) continue ;
f[k|(<<(i-))] = max( f[k|(<<(i-))] , f[k] + links[j][i] ) ;
ans = max( f[k|(<<(i-))] , ans ) ;
}
printf( "%d\n" , ans ) ;
} int main( )
{
freopen( "weapon.in" , "r" , stdin ) ;
freopen( "weapon.out" , "w" , stdout ) ;
scanf( "%d" , &t ) ;
while( t-- )
{
Init( ) ;
Solve( ) ;
}
return ;
}