題意：

給你最多10種邊長范圍在1~25的正三角形，問能不能用它們拼成一個指定邊長（指定的范圍也是1~25）的正六邊形（每種三角形使用的個數(shù)沒有限制）。圖1是一個用邊長為2和3的三角形拼成邊長為9的正六邊形的例子。

?

具體代碼：

//此題難再見坐標，其他OK。。 //dfs用小正三角覆蓋大正三角，問能否完全覆蓋 //120坐標系建立 //畫圖自己研究。。。。。。、 //逐行DFS，填完一行在下一行。從下往上 從左往右 //一個三角一個三角覆蓋 //判斷能夠覆蓋的時候，小三角不行大三角一定不行 //背包優(yōu)化。。這里沒用 , 還有一種剪枝也沒用 就是先判斷1/2 1/3 1/6的覆蓋。。。 //a[i]%a[j]==0就不要a[i]了； //注意如果sz%a[i]==0 那么直接可以了。。。。 #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cstdio>using namespace std;#define MAXN 110int sz,a[15],n,tp; int g[MAXN][MAXN];bool jud1() {for(int i=0;i<tp;i++)if(sz%a[i]==0) return true;return false; }//120度建立坐標 //橫向擴大2 縱向不便，具體理解自己畫圖 void init() {memset(g,0,sizeof(g));for(int i=1;i<=sz;i++)for(int j=1;j<=sz*2+2*i-1;j++)g[i][j]=1;for(int i=sz+1;i<=sz*2;i++)for(int j=(i-sz)*2;j<=sz*4;j++)g[i][j]=1;}bool judSZ(int x,int y,int size) {if(y+2*size-2>sz*4 || x+size-1>sz*2) return false;if(y%2==1) //倒三角 規(guī)律自己畫圖看注意列坐標 {for(int i=0;i<size;i++)for(int j=0;j<2*i+1;j++)if(!g[x+i][y+j]) return false;}else //正三角 {for(int i=0;i<size;i++)for(int j=2*i;j<2*size-1;j++)if(!g[x+i][y+j]) return false;}return true; }//覆蓋回復和上面檢查能否覆蓋一樣 void cover(int x,int y,int size) {if(y%2==1){for(int i=0;i<size;i++)for(int j=0;j<2*i+1;j++)g[x+i][y+j]=0;}else{for(int i=0;i<size;i++)for(int j=2*i;j<2*size-1;j++)g[x+i][y+j]=0;} }void remove(int x,int y,int size) {if (y%2==1){for(int i=0;i<size;i++)for(int j=0;j<2*i+1;j++)g[x+i][y+j]=1;}else{for(int i=0;i<size;i++)for(int j=2*i;j<2*size-1;j++)g[x+i][y+j]=1;} }bool dfs(int x,int y) {if(x>sz*2) return true;if(y>sz*4) return dfs(x+1,1);if(!g[x][y]){int j;for(j=y+1;y<=4*sz;y++)if(g[x][j]) break;return dfs(x,j);}for(int i=0;i<tp;i++){if(judSZ(x,y,a[i])){cover(x,y,a[i]);if(dfs(x,y+1)) return true;remove(x,y,a[i]);}elsebreak;}return false; }int main() {int cs;cin>>cs;while(cs--){cin>>sz;cin>>n;tp=0;for(int i=0;i<n;i++){scanf("%d",&a[tp++]);// if(a[tp]<=sz) tp++; }for(int i=0;i<tp;i++)for(int j=0;j<tp;j++){if(i==j) continue;if(a[i]%a[j]==0){swap(a[i],a[tp-1]);i--,tp--;break;}}sort(a,a+tp);if(jud1()){printf("YES\n");continue;}init();if(dfs(1,1)) printf("YES\n");else printf("NO\n");}return 0; } View Code

?

轉載于:https://www.cnblogs.com/baoluqi/p/3741384.html

總結

以上是生活随笔為你收集整理的poj-1069(三角形和六边形)（转）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。