首页 > 代码库 > TYVJ1190

TYVJ1190

2024-07-19 06:41:56   215人阅读

新技能get！
首先先说一个小模型吧算是，给你n个数，求这n个数能组成的数有哪些（前提n和a[i]不能太大）,这n个数的和为sum
开一个标记数组vis[i][j]表示前i个数是否可以组成j初始化vis[i][j]为0,vis[i][0]=1(0<=i<=n)（意思就是一个数也不选，组成的数为0）
然后枚举a[i]，对于每个a[i]，枚举j = sum->a[i];
for(int i = 1;i<=n;++i)
for(int j = sum;j>=a[i];--j)
if(vis[i-1][j-a[i]])
vis[i][j] = vis[i][j-a[i]] = 1;
大致分析一下这段代码，一开始标记了vis[i][0] = 1;
如果在i-1层时j-a[i] 已经出现了，那么它再加上a[i]就得j，即j可以被表示，则在第i层把j和j-a[i]两个数标记
最后扫一遍vis[n][i]就知道可以组合出哪些数了
这里因为只用到上一层的vis[][]并且不改变其值，则空间也可以优化到1维，只需要vis[j]表示j是否可以组合出j(如果是一维的话，j只能倒着枚举)
说到这里这道题的主要核心基本上说完了，好像什么都还没说？
这道题要求的是最大的相同的高度，只要求出每个城堡所能变为的高度，用cnt[]数组记录下每个高度出现的次数，则选出cnt[i]==n的i的最大值即是。

 

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 105; 7 int a[maxn],vis[10005],cnt[10005]; 8 int main() 9 {10     //freopen("in.txt","r",stdin);11     int n;12     memset(cnt,0,sizeof(cnt));13     while(cin>>n)14     {15         for(int k = 1;k<=n;++k)16         {17             memset(vis,0,sizeof(vis));18             int m = 1,t,sum = 0;19             while(~scanf("%d",&t)&&t!=-1)20             {21                 a[m++] = t;22                 sum+=t;23             }24             vis[0] = 1;25             for(int i = 1;i<m;++i)26                 for(int j = sum;j>=a[i];--j)27                     if(vis[j-a[i]])vis[j] = 1;28             for(int i = 0;i<=sum;++i)29                 if(vis[i])cnt[i]++;30         }31         for(int i = 10000;i>=0;i--)32             if(cnt[i]==n)33             {34                 printf("%d\n",i);35                 break;36             }37 38     }39     return 0;40 }

 

TYVJ1190


联系
我们