10年省赛-Greatest Number （二分+暴力） + 12年省赛-Pick apples（DP） + UVA 12325（暴力-2次枚举）

题意：给你n个数，在里面取4个数，可以重复取数，使和不超过M,求能得到的最大的数是多少；

思路：比赛时，和之前的一个题目很像，一直以为是体积为4（最多选择四次）的完全背包，结果并不是，两两求和，然后二分枚举;

完全背包是固定的体积，然后尽量使得装下的重量最大；

这个题目是固定的体积，但求在不超过该重量的情况下能得到的最大值。

至于为啥不是完全背包到现在还找到一个反例，以后再修改；

不过看到一共选择四次的时候，就应该想到是暴力。。。

比较相似的一个题目，12年的省赛题目：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2408

那个是10的8次方，也是优化之后才能背包，将10的6次方的那部分先减掉，因为它是不限制取的次数的

 #include <bits/stdc++.h>

 using namespace std;

 #define N 10010

 #define repu(i,a,b) for(int i=a;i<b;i++)

 #define ll long long

 int c[N],a[N];

 int main()

 {

     int n,m,b,kase = ,ok = ;

     while(scanf("%d%d",&n,&m)&&n&&m)

     {

         vector<int> s;

         s.clear();

         repu(i,,n)

         scanf("%d",&a[i]),s.push_back(a[i]);

         repu(i,,n)

         {

             repu(j,i,n)

             if(a[i]+a[j] <= m)

                 s.push_back(a[i]+a[j]);

         }

         sort(s.begin(),s.end());

         int ans = ;

         repu(i,,s.size())

         {

             int st = i,ed = s.size() - ;

             while(st <= ed)

             {

                 int mid = (st + ed) /;

                 if(s[mid] + s[i] > m)

                     ed = mid -;

                 else

                 {

                     if(s[i] + s[mid] > ans)

                         ans = s[i] + s[mid];

                     st = mid + ;

                 }

             }

         }

         printf("Case %d: %d\n\n",kase++,ans);

     }

     return ;

 }

Great Number

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <vector>

 #include <algorithm>

 using namespace std;

 #define N 1000005

 #define ll long long

 struct App

 {

     ll s, p;

     double k;

     bool operator < (const App& rhs) const

     {

         return k < rhs.k;

     }

 } app[];

 double d[N];

 int main()

 {

     int T;

     scanf("%d", &T);

     ll v;

     ll q = ;

     for(int cases = ; cases <= T; cases++)

     {

         memset(d, , sizeof(d));

         for(int i = ; i < ; i++) {

             scanf("%lld%lld", &app[i].s, &app[i].p);

             app[i].k = (double)app[i].p / (double)app[i].s;

         }

         scanf("%lld", &v);

         sort(app, app + );

         ll t = ;

         //printf("t : %lld\n", max(v, 1000000ll));

         if(v > q) {

             //printf("t : %lld\n", v);

             t = (v - q) / app[].s + 1ll;

             v -= t * app[].s;

         }

         //printf("%lld\n", app[2].s);

             for(int i = ; i <= v; i++)

                 for(int j = ; j < ; j++)

                   if(i - app[j].s >= )

                     d[i] = max((double)d[i - app[j].s] + (double)app[j].p, d[i]);

         printf("Case %d: %.0lf\n", cases, d[v] + (double)t * (double)app[].p);

     }

     return ;

 }

完全背包+优化

UVA 题意：给固定体积，告诉你两种物品的体积，以及他们的价值，求最多能装的价值是多大；
看似像背包，但是可以暴力做，2次枚举同时，i个s1,i个s2,同时比较，保留大的，i循环100000就够了
误解:记得之前做过，队友说看比例，即第一个物体和第二个物体比较性价比，谁的高先留谁，装不下了再考虑第二个物体，之前我很赞同，现在有反例了：9 2 5 3 7（总体积，第一物体体积，价值，第二物体体积，价值）这组样例正确答案是21，但是按照上边的思路得出的是20，因为先考虑的是第一个，所以还是应该枚举。这样想，已经在两个题目上验证是错误的，应该放弃这种思想了。。。

巴特西

10年省赛-Greatest Number （二分+暴力） + 12年省赛-Pick apples（DP） + UVA 12325（暴力-2次枚举）

最新文章

热门文章