Codeforces Round #326 (Div. 2)-Duff and Meat

题意：

　　Duff每天要吃a_i千克肉，这天肉的价格为p_i（这天可以买好多好多肉），现在给你一个数值n为Duff吃肉的天数，求出用最少的钱满足Duff的条件。

思路：

　　只要判断相邻两天中，今天的总花费 = a_i*p_i 与昨天的总花费（还有加上今天要吃的肉的重量）= （a_i-1+ a_i）*p_i-1 。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <fstream>

 #include <ctime>

 #include <cmath>

 #include <cstdlib>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <iterator>

 #include <vector>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 #define MOD 1000000007

 #define MAXN 10000010

 #define MAXM 1000010

 int main()

 {

      int n, sum, tot;

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

      {

          tot = ;

          int i;

          int a, p, x, y;

          for(i = ; i < n; i++ )

          {

              sum = ;

              scanf("%d%d", &a, &p);

              if(i == )

              {

                  sum += a*p;

                  x = a;

                  y = p;

              }

              else

              {

                  if(a*p + x*y > (x+a)*y)

                  {

                      sum += a*y;

                  }

                  else

                  {

                      sum += a*p;

                      x = a;

                      y = p;

                  }

              }

              tot += sum;

          }

          printf("%d\n", tot);

      }

      return ;

 }

第二种写法：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <fstream>

 #include <algorithm>

 #include <ctime>

 #include <cmath>

 #include <cstdlib>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <iterator>

 #include <vector>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 #define MOD 1000000007

 #define MAXN 100010

 #define MAXM 1000010

 int a[MAXN], p[MAXN], dp[MAXN];

 int main()

 {

     int n;

     int ans;

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

     {

         int i;

         ans = ;

         for(i = ; i <= n; i++ )

         {

             scanf("%d%d", &a[i], &p[i]);

             if(i == )

                 dp[i] = p[i];

             else

                 dp[i] = min(dp[i-], p[i]);

         }

         for(i = ; i <= n; i++ )

             ans += a[i]*dp[i];

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

Codeforces Round #326 (Div. 2)-Duff and Meat

最新文章

热门文章