首页 > 代码库 > TYVJ1299

TYVJ1299

2024-07-19 06:37:31   218人阅读

这题纠结了N久，就是想不通，8000个人每个人用一次8000*8000的01背包，后来看别人的题解也看不下去，然后不知道看到了点什么，突然灵光一闪，打表！
其实也不算是打表了。。一开始想不到这个主要还是因为二维的01背包用的太少了，以前都是偷懒用一维，(这里用二维的也不行，会MLE，只要把每次i循环完后的dp[Total_v])保存一下就好了，然后根据每个孩子手上的数字是多少，就能得出他的身高。
身高问题说完了，就是简单的01背包
然后求什么“环形最长上升子序列”，丫的它这么说就是坑你呢，让你往dp那方向想，仔细看题就知道，可以在这个圈里转很多很多次，每次可以只选出一个人，也就是把孩子们的身高从小到大排序，然后找出把重复的去掉，不重复的统计一下，输出就好

 

总的来说这题还是不错的，最起码让人更深的理解了01背包

 

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 8001; 7 const int maxv = 8001; 8 int dp[maxv],a[maxn],w[maxn],v[maxn],h[maxn],s[maxn]; 9 int main()10 {11     //freopen("in.txt","r",stdin);12     int n,m,c;13     cin>>n>>m>>c;14     for(int i = 1;i<=n;++i)scanf("%d",a+i);15     for(int i = 1;i<=m;++i)scanf("%d",v+i);16     for(int i = 1;i<=m;++i)scanf("%d",w+i);17     memset(dp,0,sizeof(dp));18     for(int i = 1;i<=m;++i)19     {20         for(int j = c;j>=w[i];--j)21             dp[j] = max(dp[j],dp[j-w[i]]+v[i]);22         s[i] = dp[c];23     }24     for(int i = 1;i<=n;++i)25         h[i] = s[a[i]];26     sort(h+1,h+1+n);27     int ans[maxn],cnt = 0;28     ans[cnt++] = h[1];29     for(int i = 2;i<=n;++i)30     {31         if(h[i]==h[i-1])continue;32         else ans[cnt++] = h[i];33     }34     cout<<cnt<<endl;35     for(int i = 0;i<cnt;++i)36         cout<<ans[i]<<" ";37     cout<<endl;38 39 40     return 0;41 }

 

TYVJ1299


联系
我们