用DP枚举出每一个的能到达的高度,进行 \(n\) 次背包即可,\(ans[ ]\) 记录高度 \(j\) 是否可行,高度 \(j\) 可行 \(n\) 次就是答案,\(j\) 从 \(maxn\) 开始枚举
//dp[i][j] 表示前i个表示高度为j的存不存在
// dp[i][j]=dp[i-1][j],dp[i][j]=dp[i-1][j-a[i]];选或者不选
//顺序的话dp[j-a[i]]里记录的其实是dp[i][j-a[i]]而逆序是它记录的是dp[i-1][j-a[i]]
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int dp[N];
int a[N],ans[N];
int n,maxn;
void dp_01(int g,int sum)
{
memset(dp,0,sizeof dp);
dp[0]=1,a[0]=g;
for(int i=1;i<=g;i++)
for(int j=sum;j>=a[i];j--)
{
if(dp[j-a[i]]&&!dp[j]){
dp[j]=1,ans[j]++; //高度j可行
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int g=0,sum=0;
while(true)
{
int x=0;
cin>>x;
if(x==-1) break;
a[++g]=x;
sum+=x;
}
maxn=max(maxn,sum);
dp_01(g,sum);//dp
}
for(int i=maxn;i>=0;i--)
{
if(ans[i]==n) {
cout<<i<<endl;
return 0;
}
}
cout<<"0"<<endl;
return 0;
}
标签:积木,int,sum,简略,高度,P1504,maxn,ans,dp
From: https://www.cnblogs.com/marshuo/p/17987955