#2283. 画框
画框
画框
题目描述
2014‐05‐10 第2 页,共7 页 第1 题:画框(frame),运行时限2s,内存上限128M,100 分。 【问题描述】 小T 准备在家里摆放几幅画,为此他买来了N 幅画和N 个画框。为了体现他的品味,小 T 希望能合理地搭配画与画框,使得其显得既不过于平庸也不太违和。对于第i 幅画与第j 个 画框的配对,小T 都给出了这个配对的平凡度Ai,j 与违和度Bi,j。整个搭配方案的总体不和谐 度为每对画与画框平凡度之和与每对画与画框违和度之和的乘积。具体来说,设搭配方案中第 i 幅画与第Pi 个画框配对,则总体不和谐度为 , , 1 1 * i i N N i P i P i i disharmony A B
小T 希望知道通过搭配能得到的最小的总体不和谐度是多少。
【输入格式】
输入文件名为frame.in。
输入文件第1行是一个正整数T,表示数据组数。
接下来是T组数据。
对于每组数据:
第1行是一个正整数N,表示有N对画和画框;
第2到第N+1行,每行有N个非负整数,第i+1行第j个数表示Ai,j;
第N+2到第2N+1行,每行有N个非负整数,第i+N+1行第j个数表示Bi,j。
【输出格式】
输出文件名为frame.out。
输出文件仅包含T 行,每行一个整数,表示最小的总体不和谐度。
【输入输出样例】
frame.in
frame.out
1
3
4 3 2
2 3 4
3 2 1
2 3 2
2 2 4
1 1 3
30
【样例解释】
第1幅画搭配第3个画框,第2幅画搭配第1个画框,第3幅画搭配第2个画框,则总体不和谐
度为(2+2+2)*(2+2+1)=30。
【数据范围】
对于10%的数据满足N≤10,T≤2;
对于30%的数据满足Ai,j=Bi,j;
2014‐05‐10 对于70%的数据满足N≤40; 对于100%的数据满足N≤70,T≤3,Ai,j≤200,Bi,j≤200。 【编译命令】
对于c++语言: g++ -o frame frame.cpp –lm 对于c语言: gcc -o frame frame.c –lm 对于pascal语言: fpc frame.pas
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1
3
4 3 2
2 3 4
3 2 1
2 3 2
2 2 4
1 1 3
30