2025年积、积、积木城堡！

科技前沿 • 2025-02-14 10:35 • 阅读 33

大家好，我是讯享网，很高兴认识大家。

本题选自洛谷训练场。。。传送门，点击！

First.
对于这种多过程问题，需要将其分解并进行分析。（废话）

Second.
说点实际的，关于解题思路：

讯享网

在每一组城堡高度中，需将所有的可能组合计算出来，这是便需要运用01背包的思路；
但是，又以样例数据可以看出得到的数组中会有重复的部分；
运用set去重！（~~超机智！~~）
但是要注意清空dp数组与set，不然会很鬼畜。。。。
运用一个数组，来存储出现个数，再倒序寻找（~~技巧性极高~~ ）

Third.
上代码！

 #include <iostream>     #include <cstring>     #include <set>     using namespace std;     int n;     set<int> st;     int len[110];     int sum[110];     int dp[11000];     int cnt[10010];     int hi[110][110];     int main()     {         cin>>n;         for(int i=1;i<=n;i++)         {             len[i]=1;             while(cin>>hi[i][len[i]])             {                 if(hi[i][len[i]]==-1)                     break;                 else sum[i]+=hi[i][len[i]++];             }         }         for(int k=1;k<=n;k++)         {             for(int i=0;i<len[k];i++)                 for(int j=sum[k];j>=hi[k][i];j--)                     dp[j]=max(dp[j],dp[j-hi[k][i]]+hi[k][i]);             for(int i=0;i<=sum[k];i++)             {                 if(!st.count(dp[i]))                 {                     cnt[dp[i]]++;                     st.insert(dp[i]);                 }             }             st.clear();             memset(dp,0,sizeof(dp));         }         for(int i=10000;i>=0;i--)             if(cnt[i]==n)             {                 cout<<i<<endl;                 return 0;             }     }

讯享网

Fourth.
有意见请于评论中提出，一同进步。。。。

2025年积、积、积木城堡！

相关推荐