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 。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <fstream>
 5 #include <ctime>
 6 #include <cmath>
 7 #include <cstdlib>
 8 #include <algorithm>
 9 #include <set>
10 #include <map>
11 #include <list>
12 #include <stack>
13 #include <queue>
14 #include <iterator>
15 #include <vector>
16 
17 using namespace std;
18 
19 #define LL long long
20 #define INF 0x3f3f3f3f
21 #define MOD 1000000007
22 #define MAXN 10000010
23 #define MAXM 1000010
24  
25 int main()
26 {
27      int n, sum, tot;
28      while(scanf("%d", &n)==1&&n)
29      {
30          tot = 0;
31          int i;
32          int a, p, x, y;
33          for(i = 0; i < n; i++ )
34          {
35              sum = 0;
36              scanf("%d%d", &a, &p);
37              if(i == 0)
38              {
39                  sum += a*p;
40                  x = a;
41                  y = p;
42              }
43              else
44              {
45                  if(a*p + x*y > (x+a)*y)
46                  {
47                      sum += a*y;
48                  }
49                  else
50                  {
51                      sum += a*p;
52                      x = a;
53                      y = p;
54                  }
55              }
56              tot += sum;
57          }
58          printf("%d
", tot);
59      }
60  
61      return 0;
62 }

第二种写法：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <ctime>
 7 #include <cmath>
 8 #include <cstdlib>
 9 #include <set>
10 #include <map>
11 #include <list>
12 #include <stack>
13 #include <queue>
14 #include <iterator>
15 #include <vector>
16 
17 using namespace std;
18 
19 #define LL long long
20 #define INF 0x3f3f3f3f
21 #define MOD 1000000007
22 #define MAXN 100010
23 #define MAXM 1000010
24 
25 int a[MAXN], p[MAXN], dp[MAXN];
26 int main()
27 {
28     int n;
29     int ans;
30     while(scanf("%d", &n)==1)
31     {
32         int i;
33         ans = 0;
34         for(i = 1; i <= n; i++ )
35         {
36             scanf("%d%d", &a[i], &p[i]);
37             if(i == 1)
38                 dp[i] = p[i];
39             else
40                 dp[i] = min(dp[i-1], p[i]);
41         }
42         for(i = 1; i <= n; i++ )
43             ans += a[i]*dp[i];
44         printf("%d
", ans);
45     }
46 
47     return 0;
48 }