这道题目的DP思想挺先进的,用状态DP来表示各个子巧克力块。原本是要 dp(S,x,y),S代表状态,x,y为边长,由于y可以用面积/x表示出来,就压缩到了只有两个变量,在转移过程也是很巧妙,枚举S的子集s0,然后 s1=S-s0来代表除该子集的另一个集合,接下来分两种情况,如果这个子集是通过把 S保留x,切割y,则转移到dp(s0,x)和dp(s1,x),另一种情况是转移到dp(s0,y)和dp(s1,y)。为了更加缩小状态,统一把转移方程的 x换成 min(x,sum[S]/x),sum为该状态下的面积

#include <cstdio>
#include <cstring>
#include <algorithm>
//#include <cmath>
#define N 1<<17
using namespace std;
int f[N][],sum[N];
int A[],vis[N][];
int ok(int x) //测试当前状态下是否只剩下一种巧克力,是的话,二进制状态里必定只有一个1,因此只会返回1 否则则返回其他值.
{
if (x==) return ;
return ok(x/)+(x&);//这里导致我WA了好几次,原因是没注意&的优先级低,要括号起来
}
int dp(int S,int x)
{
if (vis[S][x]) return f[S][x];
vis[S][x]=;
//int& ans=f[S][x];
if (ok(S)==) return f[S][x]=; //如果满足,则说明以及到达某块具体巧克力的状态,完成任务 return 1回去
int y=sum[S]/x;
for (int s0=S&(S-);s0;s0=S&(s0-))//枚举S的子集
{
int s1=S-s0;
if (sum[s0]%x== && dp(s0,min(x,sum[s0]/x)) && dp(s1,min(x,sum[s1]/x)))
return f[S][x]=;//这里分两种情况,分别代表两个子集的产生 是切割y 或者 切割x产生的
if (sum[s0]%y== && dp(s0,min(y,sum[s0]/y))&& dp(s1,min(y,sum[s1]/y)))
return f[S][x]=;
}
return f[S][x]=; }
int main()
{
int kase=,n,x,y;
while (scanf("%d",&n)!=EOF)
{
if (n==) break;
scanf("%d%d",&x,&y);
for (int i=;i<n;i++)
scanf("%d",&A[i]);
memset(sum,,sizeof sum);
for (int i=;i<(<<n);i++)
{
for (int j=;j<n;j++)
{
if (i&(<<j))
{
sum[i]+=A[j];
}
}
}
memset(vis,,sizeof vis);
int all=(<<n)-;
int ans=;
if (sum[all]!=x*y || sum[all]%x!=)
{
ans=;
}
else
{
ans=dp(all,min(x,y));
}
printf("Case %d: %s\n",++kase,ans==? "Yes":"No");
}
return ;
}

最新文章

  1. PHP 根据key 给二维数组分组
  2. CSS控制TD内的文本超出指定宽度后不换行而用省略号代替
  3. 看我是一只IT小小鸟有感
  4. 【自动化测试】Xpath学习
  5. 数据库 SQL :有关 NULL 值引发 TRUE、FALSE、UNKNOW 三值逻辑
  6. maven常用插件配置详解
  7. 2016022607 - redis配置文件
  8. DIV布局之道三:DIV块的覆盖,DIV层遮盖其他DIV
  9. Windows 8实例教程系列 - 数据绑定基础实例
  10. php 依赖注入容器
  11. 聊聊keep-alive组件的使用及其实现原理
  12. saiku应用的调试
  13. toFixed()一不小心踩了一个坑
  14. 02-MySQL基础
  15. 加密解密DES之Android、IOS、C#实现
  16. python之路——12
  17. LeetCode – Number of Islands II
  18. 公共技术点(Android 动画基础)
  19. MyCat - 背景篇(1)
  20. adb root : adbd cannot run as root in production builds

热门文章

  1. ACM-挑战题之排列生成
  2. 整合 nginx php-fpm
  3. chatdet用法
  4. MQTT 协议学习:Retained(保留消息) 与 LWT(最后遗嘱)
  5. 【LeetCode】接雨水
  6. 七十二、SAP中内表的修改,添加条件语句,多条目修改
  7. IISHelper操作iis
  8. Java 归并排序
  9. js利用递归生成随机数填充到数组
  10. torch.cuda.FloatTensor