电子元器件商城网站建设,wordpress++压缩,楚雄市住房和城乡建设局门户网站,凡科建设网站如何对话框正题 题目大意
若干根棍子#xff0c;不能折#xff0c;不能多余求能够组成的最大长方形。 解题思路
首先我们发现如果棍子集合SSS长度为lll且它有子集GGG长度为l2\frac{l}{2}2l那么就表示这个集合的棍子可以作为一个矩形的对应两边#xff0c;这样我们只要枚举两个不相…正题 题目大意
若干根棍子不能折不能多余求能够组成的最大长方形。 解题思路
首先我们发现如果棍子集合SSS长度为lll且它有子集GGG长度为l2\frac{l}{2}2l那么就表示这个集合的棍子可以作为一个矩形的对应两边这样我们只要枚举两个不相交集合作为长宽就好了。
我们设gig_igi表示二进制表示的集合iii十分可以折半。我们预处理ggg数组对于每个集合我们做一个背包预处理就好了。
然后dfsdfsdfs那些边作为长那些边做宽就可以了。
时间复杂度:O(2nnl3n)O(2^nnl3^n)O(2nnl3n) 但实际上远远达不到这个复杂度 codecodecode
#includecstdio
#includealgorithm
#includecstring
using namespace std;
int n,a[20],MS,f[3000],g[117],ans;
void dfs(int dep,int c1,int c2,int len,int wigh)
{if(len*wighansg[c1]g[c2])anslen*wigh;if(depn) return;dfs(dep1,c1|(1dep),c2,lena[dep],wigh);dfs(dep1,c1,c2|(1dep),len,wigha[dep]);dfs(dep1,c1,c2,len,wigh);
}
int main()
{scanf(%d,n);for(int i0;in;i)scanf(%d,a[i]);MS1n;for(int i1;iMS;i){memset(f,0,sizeof(f));int sum0;f[0]1;for(int j0;jn;j)if(i(1j)) suma[j];if(sum%2) continue;for(int j0;jn;j)if(i(1j)){for(int ksum/2;ka[j];k--)f[k]|f[k-a[j]];}if(f[sum/2]) g[i]1;}dfs(0,0,0,0,0);if(!ans) printf(No Solution);else printf(%d,ans/4);
}
