唔..这题…
首先是个很明显的背包什么呀,明明是很明显的暴搜
设f[x]=0:不可以拼出x;f[x]=1:可以拼出x
每考虑一块大理石(价值是$i$),$f[j]|=f[j-i]$就好了
最后能分成两段相同价值,当且仅当价值和$sum$为偶数,且$f[sum/2]=1$
然后..就T飞了.因为这样对每一块大理石做一次背包,时间复杂度最坏$O(nm)$,$n$是大理石数量,$m$是可能的最大价值(这里就是$20000*6=120000$)
那咋办?那就二进制分解每一种价值的大理石数量,然后做背包,时间复杂度降为$O(logn\times m)$
可是…exe你快点啊,exe你别磨磨蹭蹭的…
Time Limit Exceeded
???为啥过不去啊..
那我们来一个终极优化吧.改变状态的定义,设f[x]表示拼成x后,当前的大理石最多还能剩下几块,特别地,不能拼成就是-1
状态转移变成这样(当前考虑的大理石价值为$i$,有x块):
$f[j]=x\ (f[j]\ge 0)$本来就可以拼成,那么现在的大理石都可以剩下.
$f[j]=f[j-i]-1\ (f[j]=-1,j\ge i,f[j-i]>0)$本来不能拼成,但用了一块就能拼成了.
$f[j]=-1\ (otherwise)$ 除了上述两种情况,都不能拼成.
最后时间复杂度$O(m)$.$m$是可能的最大价值(这里就是$20000*6=120000$)
/**********/省略快读
#define MAXN 120011
ll f[MAXN];
int main()
{
while(1)
{
memset(f,-1,sizeof f);
f[0]=0;
ll sum=0;
for(ll i=1;i<=6;++i)
{
ll x=read();
sum+=x*i;
for(ll j=0;j<MAXN;++j)
{
if(f[j]>=0)f[j]=x;
else if(j>=i&&f[j-i]>0)f[j]=f[j-i]-1;
else f[j]=-1;
}
}
if(!sum)break;
puts(!(sum&1)&&f[sum>>1]>=0?"Can":"Can't");
}
return 0;
}
状态太妙了,%%%
题主优化的处理很妙~
但二进制分解后背包的复杂度是对的呀,应该是可以过的
我当时T了....难受
可能是多组数据的原因吧
然而另一篇题解只用二进制拆分就过了是什么操作啊