本文共 3041 字，大约阅读时间需要 10 分钟。
这道题也是usaco上的题，所以有测试数据，帮着调试了两个bug。
题中已经给出了所有的6种情况（4和5是一样的），所以按照这六种情况尝试就好了。
对每种情况，矩形有不同的排列。比如case1是1种，case2是4种，case3是C_4^2，case4case5是c_4^2，case6是全排列。
矩形本身有可以旋转，所以四个矩形关于旋转与否有2^4=16种状态。
然后就是罗列上述情况，记录最小面积（及对应的宽）就可以了。
#include #include #include #include #include #include using namespace std;void check(int wid, int hig, int &minarea, vector > &sols){ int area = wid * hig; if(area < minarea) { minarea = area; sols.clear(); sols.push_back(make_pair (wid, hig)); } else if(area == minarea) { sols.push_back(make_pair (wid, hig)); }}int main(){ //FILE *fin, *fout; //fin = fopen("packrec.in", "r"); //fout = fopen("packrec.out", "w"); //assert(fin != NULL && fout != NULL); int sqs_in[4][2]; for(int i = 0; i < 4; ++i) { for(int j = 0; j < 2; ++j) { //fscanf(fin, "%d", &sqs_in[i][j]); fscanf(stdin, "%d", &sqs_in[i][j]); } } int minarea = 50 * 4 * 50 * 4; vector > sols; int sqs[4][2]; for(int per = 0; per < 16; ++per) { int tmp = per; for(int bit = 0; bit < 4; ++bit) { if(tmp % 2 == 0) { sqs[bit][0] = sqs_in[bit][0]; sqs[bit][1] = sqs_in[bit][1]; } else { sqs[bit][0] = sqs_in[bit][1]; sqs[bit][1] = sqs_in[bit][0]; } tmp >>= 1; } int sumw = 0; for(int i = 0; i < 4; ++i) sumw += sqs[i][0]; //case 1 int wid = sumw; int hig = sqs[0][1]; for(int i = 1; i < 4; ++i) { if(sqs[i][1] > hig) hig = sqs[i][1]; } check(wid, hig, minarea, sols); //case 2 for(int i = 0; i < 4; ++i) { wid = sumw - sqs[i][0]; wid = max(wid, sqs[i][1]); hig = -1; for(int j = 0; j < 4; ++j) { if(j != i && sqs[j][1] > hig) hig = sqs[j][1]; } hig += sqs[i][0]; check(wid, hig, minarea, sols); } //case 3 for(int i = 0; i < 4; ++i) { for(int j = i + 1; j < 4; ++j) { for(int k = 0; k < 2; ++k) { int l = (k == 0? i : j); int r = (k == 0? j : i); wid = max(sqs[l][1] + sqs[r][0], sumw - sqs[l][0]); hig = sqs[r][1]; for(int t = 0; t < 4; ++t) { if(t != l && t != r && sqs[l][0] + sqs[t][1] > hig) { hig = sqs[l][0] + sqs[t][1]; } } check(wid, hig, minarea, sols); } } } //case 4 && case 5 for(int i = 0; i < 4; ++i) { for(int j = i + 1; j < 4; ++j) { wid = sumw - min(sqs[i][0], sqs[j][0]); hig = sqs[i][1] + sqs[j][1]; for(int k = 0; k < 4; ++k) { if(k != i && k != j && sqs[k][1] > hig) hig = sqs[k][1]; } check(wid, hig, minarea, sols); } } //case 6 int arr[4] = {0, 1, 2, 3}; do { wid = max(sqs[arr[0]][0] + max(sqs[arr[3]][0], sqs[arr[1]][1]), sqs[arr[2]][0] + sqs[arr[3]][0]); hig = max(sqs[arr[0]][1] + sqs[arr[2]][1], sqs[arr[1]][0] + max(sqs[arr[2]][1], sqs[arr[3]][1])); check(wid, hig, minarea, sols); }while(next_permutation(arr, arr + 4)); } //fprintf(fout, "%d\n", minarea); fprintf(stdout, "%d\n", minarea); vector wids; for(int i = 0; i < sols.size(); ++i) { wids.push_back(min(sols[i].first, sols[i].second)); } sort(wids.begin(),wids.end()); //fprintf(fout, "%d %d\n", wids[0], minarea / wids[0]); fprintf(stdout, "%d %d\n", wids[0], minarea / wids[0]); for(int i = 1; i < wids.size(); ++i) { if(wids[i] != wids[i - 1]) { fprintf(stdout, "%d %d\n", wids[i], minarea / wids[i]); } } return 0;}
转载地址：http://txxli.baihongyu.com/