Description
【问题描述】
如图是某人设想中的N×N的密码盘，用以显示自己强大的智商以及计算能力。图中每列上面有一个0或1的值，每行左边也有一个0或1的值。密码盘中有最多N*N个按钮，每个按钮有一个数值。按钮按下去之后，你会获得按钮上的分数，然后对应行和对应列的值会改变。
例如：假设按钮（1，4）的数值为k，按下它，你获得k分，然后第一行的1会变成0，第四列的0会变成1。
你的任务是，使每列上面的值和每行左边的值一一对应相等（从左到右和从上到下），并且取得最大的积分。当然了初始积分为0。
Input
【输入】
输入文件名为mima.in。
第一行一个正整数N，表示密码盘的大小。N最大为9。
第二行一个01串，表示从上到下每行左边的N个值。
第三行一个01串，表示从左到右每列上边的N个值。
下一行一个正整数k，表示按钮的数量。1≤k≤N*N。
接下来k行，每行三个整数a、b、c，表示第a行第b列处有一个数值为c的按钮。左上角的格子为第一行第一列。1≤a≤N，1≤b≤N，-100≤C≤100。不会有同一个地方出现两个按钮。
Output
【输出】
输出文件名为mima.out
输出一行，包含一个整数，表示所能取得的最大积分。如果不能使得每列上面的值和每行左边的值一一对应相等，输出“I am stupid!”。
Sample Input
6
110111
101010
7
5 2 1
3 3 -1
1 4 2
3 5 -2
5 4 3
5 5 -3
6 5 4
Sample Output
6
Data Constraint
Hint
【注释】
样例中除图中灰色的按钮以外，全部都按下。共10个测试数据。
对于第i个测试数据，N=Max{ 3 , Min{ i , 9 }}。
题解
f[i,j,l]=max(f[l?1,x,y]+a[l],f[i,j,k])表示f[i,j]通过选或不选a[l]变成f[x,y]。
代码
type
arr=record
x,y,w:longint;
end;
var
n,m,nm,l:longint;
sum:int64;
f:array[0..1000,0..1000,0..1] of longint;
a:array[0..1000] of arr;
function max(x,y:longint):longint;
begin
if x>y then exit(x)
else exit(y);
end;
procedure init;
var
i,j,x,y,z:longint;
begin
readln(n);
nm:=1 shl n-1;
readln(z);
x:=0;y:=0;
for i:=n downto 1 do
begin
x:=x+z mod 10 shl (i-1);
z:=z div 10;
end;
readln(z);
for i:=n downto 1 do
begin
y:=y+z mod 10 shl (i-1);
z:=z div 10;
end;
for i:=0 to nm do
for j:=0 to nm do
f[i,j,0]:=-maxlongint div 5;
f[x,y,0]:=0;
readln(m);
for i:=1 to m do
with a[i] do
readln(x,y,w);
end;
procedure main;
var
i,j,k,v,u:longint;
begin
for k:=1 to m do
begin
l:=l xor 1;
for i:=0 to nm do
for j:=0 to nm do
with a[k] do
begin
u:=i xor 1 shl (x-1);
v:=j xor 1 shl (y-1);
f[i,j,l]:=max(f[i,j,l xor 1],f[u,v,l xor 1]+w);
end;
end;
end;
var
i:longint;
begin
init;
main;
sum:=-maxlongint div 5;
for i:=0 to nm do
sum:=max(sum,f[i,i,l]);
if sum>=-100 then write(sum)
else write('I am stupid!');
end.