【985系列】985的买饮料难题

Problem E: 985的买饮料难题

Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 240   Solved: 128 Submit Status Web Board

Description

天气太热了，985制定了对未来的规划即第i天喝a[i]瓶饮料。为了节约开支，他打听到了第i天每瓶饮料的价格p[i]。 为了不让自己的规划落空，他想知道这n天他至少要花多少钱。 精明的985可以选择在任意一天买数目不限的饮料，而且他有一个神奇的冰箱，可以将提前购买的饮料保存下来（至少在这n天里是可以饮用的）。

Input

第一行输入一个整数t，代表有t组测试数据。 每组数据第一行输入一个整数n代表规划的总天数，接下来有n行，每行输入两个整数a[]，p[]分别代表上面提到的信息。 注：1 <= t <= 30，1 <= n <= 1000，1 <= a[]，p[] <= 100。

Output

输出一个整数代表最后的结果。

Sample Input

2 2 25 56 94 17 5 39 21 95 89 73 90 9 55 85 32

Sample Output

2998 6321

HINT

Submit Status Web Board

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int N = 1000+10; int a[N],p[N],vis[N]; int main() { int T; scanf("%d",&T); while(T--) { int n,sum=0; scanf("%d",&n); for(int l=1; l<=n; l++) scanf("%d%d",&a[l],&p[l]); int flag=1,cnt; cnt=p[1]; vis[0]=1; for(int l=2; l<=n; l++) { if(p[l]<cnt) { cnt=p[l]; vis[flag]=l; flag++; } } vis[flag]=n+1; int t; for(int l=0; l<flag; l++) { t=vis[l]; for(int j=t; j<vis[l+1]; j++) { sum=sum+p[t]*a[j]; } } printf("%d\n",sum); } return 0; } /************************************************************** Problem: 1896 Language: C++ Result: Accepted Time:7 ms Memory:884 kb ****************************************************************/