题目

http://www.tyvj.cn/p/1015

http://www.tyvj.cn/p/1016

http://www.tyvj.cn/p/1017

http://www.tyvj.cn/p/1018

题解

1015

背包dp, 转移方程f[i + j] = min(f[i + j], f[i] + c[j])

答案:

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int c[11], f[105];
int n;
int i, j;
int main()
{
    for(i = 1; i <= 10; ++i)
        scanf("%d", &c[i]);
    scanf("%d", &n);
    memset(f, 127, sizeof(f));
    f[0] = 0;
    for(j = 1; j <= 10; ++j)
        for(i = 0; i <= n; ++i)
            if(f[i] < 1000000)
                f[i + j] = min(f[i + j], f[i] + c[j]);
    printf("%d", f[n]);
    return 0;
}

1016

最标准的背包, 转移方程f[i]放入东西i个最大占用空间

//似乎WA了…不过也无所谓了…= =

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int v, n;
int d[35], f[35];
int i, j;
int main()
{
    scanf("%d%d", &v, &n);
    for(i = 1; i <= n; ++i)
        scanf("%d", &d[i]);
    f[0] = 0;
    for(i = 0; i <= n; ++i)
        for(j = n; j >= 1; --j)
            if(f[i] + d[j] < v)
                f[i + 1] = max(f[i + 1], f[i] + d[j]);
    printf("%d", v - f[n]);
    return 0;
}

1017

简单的并查集问题, 在kruskal算法里面也有用到

不同集合(等价类)不停合并, 合并失败则计数器自增

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n, m, ans;
int a[1005];
int i, j, w, l;
int main()
{
    scanf("%d%d", &n, &m);
    for(i = 1; i <= m; ++i)
        a[i] = i;

    for(i = 1; i <= n; ++i){
        scanf("%d%d", &w, &l);
        if(a[w] == a[l]) ans++;
        for(j = 1; j <= m; ++j)
            if(a[j] == a[w] && j != w) a[j] = a[l];
        a[w] = a[l];
    }
    printf("%d", ans);
    return 0;
}

1018

按照正常的思路走..答案用long long存储

#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
int n, k;
int a[25];
int i, j, w;
ll ans = 1;
int main()
{
    scanf("%d%d", &n, &k);
    for(i = 1; i <= n; ++i)
        ans *= i;
    while(!(ans % 10)) ans /= 0;  //去尾0
    while(ans){
        a[++w] = ans % 10;  //按位保存
        ans /= 10;
    }
    for(i = min(w, k); i >= 1; --i)
        printf("%d", a[i]);  //尾部输出
    return 0;
}