這個(gè)題糾結(jié)了好久。首先想到的是暴搜，必超時(shí)。
然后注意到題目中，天平左邊的物體和右邊的物體交替取，可能會(huì)使更快得到最優(yōu)解，所以就根據(jù)他們的位置是否>0把他們放到兩個(gè)數(shù)組里，這里有個(gè)優(yōu)化就是按照到達(dá)-1.5和+1.5的力矩排序，這樣如果取了前面的物體天平失去了平衡，則后面的物體也不用取了，一定會(huì)失去平衡。這樣繼續(xù)暴搜，還是超時(shí)。我估計(jì)這個(gè)優(yōu)化沒什么用，因?yàn)榫退隳惆咽Ｏ碌亩既⊥辏膊恍枰速M(fèi)多少時(shí)間嘛。。。平均意義上能減少一般的時(shí)間。但是A(20,20)。。這個(gè)有點(diǎn)大。
好吧，又繼續(xù)陷入僵局了。看別人的結(jié)題報(bào)告，發(fā)現(xiàn)主流版本是一堆亂糟糟的代碼，不懂在搞什么。。。后來偶然發(fā)現(xiàn)了一個(gè)版本，在暴搜的時(shí)候，寫的很奇怪，參見http://blog.csdn.net/wuli2496/article/details/7284641。dfs(l,r)，l,r表示前面l-1,r-1個(gè)已經(jīng)取過了，這讓我煞是費(fèi)解。（他的解法是把物體一個(gè)個(gè)的放到糾結(jié)的天平上），為什么不能先力矩放大的，后放力矩小的？然后我改了下他的dfs()，變成無參的，每次都從0開始找，交，超時(shí)了。作者沒有說明他為什么要這么做，或許是他不想說？或者他沒留意？而且這明明就不是個(gè)dfs了，如果可以證明，先放小的比先放大的好，那么這個(gè)dfs就是個(gè)DP了。和有限背包問題一樣的。好吧。然后我就想著證明為何先放力矩小的比先放力矩大的好，想了很久，發(fā)現(xiàn)，沒辦法。
后來，偶然想到了一種方法，證明出如果在當(dāng)前的情況中，拿掉左邊力矩最大的，天平向右歪，并且拿掉右邊力矩最大的，天平向左歪，那么無論以后怎么拿，都不可能成功。
這樣反推一下，剛剛好是一個(gè)dp。r[i][j]表示放上去了左邊前i個(gè)，右邊前j個(gè)的天平狀況（這種狀況剛剛好依賴于0-i,0-j的質(zhì)量）。它只能由r[i][j-1],r[i-1][j]推出。
額，這樣就是一個(gè)完美的背包問題了，只要20*20個(gè)狀態(tài)，交了，A掉了，跑的足夠快，理論上應(yīng)該是最快的解法了吧？肯定比搜索快，也要比狀態(tài)壓縮的DP快，因?yàn)闋顟B(tài)壓縮的DP需要2^20個(gè)狀態(tài)。。。可能是我的代碼寫的太亂了，所以才跑到15名。。
好了，最重要的的問題就是證明上面一段中紅色字的結(jié)論。
現(xiàn)在我們把天平分成3段：第一段是最左邊到-1.5，中間是-1.5到1.5，右邊是1.5-最右邊。
左邊的物體的力矩我們記為:WL(左邊最大那個(gè)力矩) + Lrest(左邊剩余力矩) ,中間的物體的力矩我們記為 C+Mrest(C表示中間那一段的模板質(zhì)量，Mrest表示中間物體質(zhì)量),右邊的力矩我們記為
WR(右邊最大那個(gè)力矩)+Rrest(右邊剩余力矩)。我們可以簡(jiǎn)單地在左邊和右邊都剪掉Rrest。那么左邊，中間，右邊的力矩為WL+rest, C+Mrest,WR。如果拿掉左邊最大的右偏，我們可以得到式子 : rest + C + Mrest < WR 。那么很顯然，rest會(huì)越來越小，所以這個(gè)式子永遠(yuǎn)成立，所以紅字得證。
好了，這個(gè)證明想了很久，而且中間用到了一個(gè)結(jié)論：拿掉天平左右兩邊等重的物體，對(duì)天平?jīng)]影響。對(duì)于有兩個(gè)平衡點(diǎn)的這只是個(gè)臆測(cè)，額好吧，誰有更好更簡(jiǎn)單的解法歡迎交流。LRJ出的題果真很神，不過也很讓人糾結(jié)。代碼寫的比較亂，莫看。
#include <cstdio>
#include <cstdlib>
#include <cstring>
class node
{
public:
int pos,w;
};
class set
{
public:
int ll,lr,rl,rr;
int prev,ok;
};
set res[30][30];
node lefts[110],rights[110];
int lcount,rcount;
int find;
int L,W,C;
int abs(int i)
{
if(i>0) return i;
return -i;
}
void pans(int l,int r)
{
if(l == 0 && r== 0)
return;
if(res[l][r].prev == 1)
{
printf("%d %d\n",rights[r-1].pos/2,rights[r-1].w);
pans(l,r-1);
}
else
{
printf("%d %d\n",lefts[l-1].pos/2,lefts[l-1].w);
pans(l-1,r);
}
}
int cmp1(const void* a,const void* b)
{
node i = *(node*)a;
node j = *(node*)b;
return (-i.pos-3)*i.w - (-j.pos-3)*j.w;
}
int cmp2(const void* a,const void* b)
{
node i = *(node*)a;
node j = *(node*)b;
return (i.pos-3)*i.w - (j.pos-3)*j.w;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int i,c=1,j;
int ll,lr,rl,rr;
while(scanf("%d%d%d",&L,&W,&C)!=EOF && L>0)
{
memset(res,0,sizeof(res));
L *= 2;
ll = rr =0; rl = lr = 3*W;
node tmp;
lcount = rcount = 0;
for(i=0;i<C;i++)
{
scanf("%d%d",&tmp.pos,&tmp.w);
tmp.pos*=2;
if(tmp.pos<0)
lefts[lcount++] = tmp;
else
rights[rcount++] = tmp;
}
qsort(lefts,lcount,sizeof(node),cmp1);
qsort(rights,rcount,sizeof(node),cmp2);
set tmpset = {ll,lr,rl,rr,0,1};
res[0][0] = tmpset;
for(i=0;i<=lcount;i++)
for(j=0;j<=rcount;j++)
{
if(i-1>=0 && res[i-1][j].ok == 1)
{
tmpset = res[i-1][j];
//放了第i個(gè)物體
if(lefts[i-1].pos < -3)
tmpset.ll += (-3-lefts[i-1].pos)*lefts[i-1].w;
else
tmpset.lr += (lefts[i-1].pos+3)*lefts[i-1].w;
if(lefts[i-1].pos < 3)
tmpset.rl += (3 - lefts[i-1].pos)*lefts[i-1].w;
else
tmpset.rr += (lefts[i-1].pos - 3)*lefts[i-1].w;
if(tmpset.ll < tmpset.lr && tmpset.rl>tmpset.rr)
{
tmpset.ok = 1;
tmpset.prev = -1;
res[i][j] = tmpset;
}
else
{
res[i][j].ok = 0;
}
}
if(res[i][j].ok)
continue;
if(j-1>=0 && res[i][j-1].ok == 1)
{
tmpset = res[i][j-1];
if(rights[j-1].pos < -3)
tmpset.ll += (-3-rights[j-1].pos)*rights[j-1].w;
else
tmpset.lr += (rights[j-1].pos+3)*rights[j-1].w;
if(rights[j-1].pos < 3)
tmpset.rl += (3 - rights[j-1].pos)*rights[j-1].w;
else
tmpset.rr += (rights[j-1].pos - 3)*rights[j-1].w;
if(tmpset.ll < tmpset.lr && tmpset.rl>tmpset.rr)
{
tmpset.ok = 1;
tmpset.prev = 1;
res[i][j] = tmpset;
}
else
{
res[i][j].ok = 0;
}
}
}
printf("Case %d:\n",c++);
if(res[lcount][rcount].ok == 1)
pans(lcount,rcount);
else
printf("Impossible\n");
}
return 0;
}