2020 -5

5-27 货币系统

题面看题。
完全背包问题。对原货币面额从小到大排个序。dp[j]表示在已选的货币面额种类中，能否表示出j。那么扫描数组a，对于a[i]，若dp[a[i]] = true，即能表示出，那自然该货币就可以跳过了；否则加入该货币，m++，同时更新一下dp。

#include <bits/stdc++.h>
using namespace std;
int n, m, maxx;
int a[105];
bool dp[250];
int main(){
    int t;
    scanf ("%d", &t);
    while (t--){
        m = 0;
        memset (dp, 0, sizeof dp);
        scanf ("%d", &n);
        for (int i=1;i<=n;i++)  scanf ("%d", a+i);
        sort (a+1, a+n+1);
        dp[0] = true;
        for (int i=1;i<=n;i++){
            if (!dp[a[i]]){
                m++;
                for (int j=a[i];j<=a[n];j++)
                    dp[j] |= dp[j-a[i]];
            }
        }
        printf ("%d\n", m);
    }
    return 0;
}

5-28 Protecting the Flowers

题意：有n头牛在吃可爱的花朵，现要把这些牛一头一头的迁回牛棚去，目的是使吃的花朵数量最少。每次只能牵一头牛，且牵这头牛的同时，其它的牛也在吃花。每头牛有两个参数：t, d。t是把这头牛牵回到牛棚的时间，d是这头牛单位时间内吃的花朵数量。
(注意把一头牛牵回牛棚的时间为t，再从牛棚回来还需要t时间)
输入n，然后每行为t，d。输出被吃花朵数量的最小值。

典型的贪心：我们先考虑只有两头牛时，先牵第一头牛的代价是2*t1*d2，先牵第二头牛的代价是2*t2*d1。那么要先牵那一头回去呢？使得前者的解优与后者的条件是：t1*d2 < t2*d1.
已经明了，那么根据这个条件来sort一下，统计答案即可！
牵牛的顺序就是 1->n

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
struct node{
    ll t, d;
}a[maxn];
int n;
bool cmp(node a, node b){
    return a.t*b.d < a.d*b.t;
}
int main(){
    ll ans = 0, sum = 0;
    scanf ("%d", &n);
    for (int i=1;i<=n;i++){
        scanf ("%lld %lld", &a[i].t, &a[i].d);
    }
    sort (a+1, a+n+1, cmp);
    for (int i=n;i>=1;i--){
        ans += 2 * a[i].t * sum;
        sum += a[i].d;
    }
    printf ("%lld", ans);
    return 0;
}