APIO2015巴厘岛的雕塑——数位DP
标签：ring one 要求 namespace 状态 枚举 turn blank 可行性
题目：https://www.luogu.org/problemnew/show/P3646
对于A>1，将答案各位全置1，然后从高位到低位改成0判断是否可行；
用f[i][j]数组代表前i个数分成j组是否可行，转移是枚举最后一段的左端点k，然后看看后面整个一段的和能否满足要求，如果前后都满足就表示i,j状态也可行；
对于A=1，可以贪心地认为分组数量越少越好，所以可行性转化为最优性，省去一维，转移条件同上，取min即可；
先写了个WA一半的版本：
#include
#include
#includeusing namespace std;
typedef long long ll;
int n,A,B,len;
ll f2[2005],ans,s[2005];
bool f[105][105];//可行性
bool dp1(ll x)
{
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1;i//前i个数分成j段
for(int j=1;j)
for(int k=0;k//0
if(((s[i]-s[k])|x)==x)f[i][j]|=f[k][j-1];
for(int i=A;i)
if(f[n][i])return 1;
return 0;
}
bool dp2(ll x)
{
// memset(f2,0x3f,sizeof f2);
f2[0]=0;
for(int i=1;i)
{
ll ad=n+1;
for(int j=0;j//0
if(((s[i]-s[j])|x)==x)ad=min(ad,f2[j]);
f2[i]=ad+1;
}
return f2[n]B;
}
int main()
{
scanf("%d%d%d",&n,&A,&B);
for(int i=1;i)
scanf("%lld",&s[i]);
for(int i=1;i)
s[i]+=s[i-1];
for(len = 0;(1LL //位数
if(A!=1)
{
ans=(ll)(11));ans--;
for(int k=len;k>=0;k--)//0!
{
ll tmp=ans-(ll)(1k);
if(dp1(tmp))ans=tmp;
}
}
else
{
ans=(ll)(11));ans--;
for(int k=len;k>=0;k--)
{
ll tmp=(ll)ans-(1k);
if(dp2(tmp))ans=tmp;
}
}
printf("%lld",ans);
return 0;
}
囧
后来又直接改成别的写法A的，但还是不太明白原来的写法为什么不行，有什么不同。
代码如下：
#include
#include
#includeusing namespace std;
typedef long long ll;
int n,A,B,len;
ll f2[2005],ans,s[2005];
bool f[105][105];//可行性
ll dp1()
{
ans=0;
for(int t=len;t>=0;t--)
{
ans+=(1LL1;
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1;i//前i个数分成j段
for(int j=1;j)
for(int k=0;k//0
if(((s[i]-s[k])|ans)==ans)f[i][j]|=f[k][j-1];
bool fl=0;
for(int i=A;if[n][i];
if(fl)ans-=(1LL1;
else ans++;
}
return ans;
}
ll dp2()
{
ans=0;
for(int t=len;t>=0;t--)
{
ans+=(1LL1;
f2[0]=0;
for(int i=1;i)
{
ll ad=n+1;
for(int j=0;j//0
if(((s[i]-s[j])|ans)==ans)ad=min(ad,f2[j]);
f2[i]=ad+1;
}
if(f2[n]1;
else ans++;
}
return ans;
}
int main()
{
scanf("%d%d%d",&n,&A,&B);
for(int i=1;i)
scanf("%lld",&s[i]);
for(int i=1;i)
s[i]+=s[i-1];
for(len = 0;(1LL //位数
if(A==1)printf("%lld",dp2());
else printf("%lld",dp1());
return 0;
}
APIO2015巴厘岛的雕塑——数位DP
标签：ring one 要求 namespace 状态 枚举 turn blank 可行性
原文地址：https://www.cnblogs.com/Zinn/p/8971746.html
评论