題目的意思大概就是給一個長方體的長寬高,問他能不能用一個w*h的紙剪出來,就是說展開圖的長寬能不能比給定的小.
題目給了11中展開圖的拓撲結構,我覺得這個很關鍵,要是題目沒有給這個我可能想不到那么全面,不過題目已經給了我就分析那11個圖形,發現展開圖的長寬大概分為三類
假設長寬高為a,b,c,具體是多少并不重要,重要的是類別,具體的數值我們枚舉一下排列就可以覆蓋所有情況.
- 一邊為 a+c+a+c,就是最長有四個連續的展開圖的那些情況
另一個邊的情況有a+b+c,b+c+c,a+a+b三種.雖然具體數值沒有意義,但是符號是有意義的.如果一個邊是a+c+a+c這就意味著我們認為b是中間他們四個共同的邊,那么b就不能出現兩次.但是其他兩個位置放置不同就會不一樣. - 一邊為a+b+c+a,就是最長有三個連續展開圖的情況.另一個邊可能為a+b+c,b+c+c,a+a+b,同樣不可能出現b出現兩次的情況
- 一邊為a+b+c+a+a,另一邊為b+c
然后我們枚舉排列,判斷每一個排列是否存在情況滿足條件
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cctype>
#include<queue>
#include<set>using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+5;int a[10];
int w,h;bool deal()
{int x,y,z;int w1,h1,h11,h12,h13,w2,h2,h21,h22,w3,h3;for(int i=0;i<3;i++){x=a[i];for(int j=0;j<3;j++){if(j==i) continue;y=a[j];for(int k=0;k<3;k++){if(k==j || k==i) continue;z=a[k];w1=x+x+z+z; h11=y+z+z; h12=x+y+z; h13=x+x+y;h1=min(h11,h12); h1=min(h1,h13);if(w1<=w && h1<=h || w1<=h && h1<=w) return true;w2=x+y+z+x; h21=x+y+z; h22=y+y+z;h2=min(h21,h22);if(w2<=w && h2<=h || w2<=h && h2<=w) return true;w3=x+y+z+x+x; h3=y+z;if(w3<=w && h3<=h || w3<=h && h3<=w) return true;}}}return false;
}int main()
{while(~scanf("%d%d%d",&a[0],&a[1],&a[2])){scanf("%d%d",&w,&h);if(deal()){printf("Yes\n");}else{printf("No\n");}}return 0;
}
)
)