vijosP1059 积木城堡

vijosP1059 积木城堡

链接:https://vijos.org/p/1059

【思路】

01背包。

刚开始想麻烦了,想的是二分答案然后01背包判断是否可行,但是首先答案不满足单调性所以不能二分(这点以后做题之前一定要想清楚),其次如果从大到小枚举依次判定的话会TLE。

不得不说自己真是笨。

其实可以对每一组积木用一次01背包,用一个cnt记录满足该高度的城堡数目。然后从大到小检查如果为n输出即可。时间上是O(n^3)。

【代码】

 #include<iostream>
#include<cstring>
#define FOR(a,b,c) for(int a=(b);a<(c);a++)
using namespace std; const int maxn = +; int h[maxn][maxn],sum[maxn];
bool d[maxn*maxn];
int cnt[maxn*maxn];
int n; void dp(int tot,int* A) {
int len=A[];
d[]=true;
FOR(i,,len)
for(int j=tot;j>=A[i];j--)
{
d[j] = d[j] || d[j-A[i]];
}
FOR(i,,tot+) cnt[i] += d[i];
} int main() {
ios::sync_with_stdio(false);
cin>>n;
int x,R=;
FOR(i,,n) {
h[i][]=;
while(cin>>x && x!=-) {
h[i][h[i][]++]=x;
sum[i] += x;
}
R=max(R,sum[i]);
} FOR(j,,n)
{
memset(d,,sizeof(d));
dp(sum[j],h[j]);
}
for(int i=R;i>=;i--)
if(cnt[i]>=n) {
cout<<i<<"\n";
break;
}
return ;
}
上一篇:[React Native] Using the Image component and reusable styles


下一篇:html 输入框 只能输入数字 只能输入字母数字组合