题目

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

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

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

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

题解

1005

比较经典的背包DP问题, 容量m kg的背包如何装最多价值的物品.

主要思路还是保存一个从1-m的序列, 表示k kg的背包能装最多价值的东西, f(k)表示当前价值, 那么第(k + j) kg的背包能装最多价值的东西便是max(f(k + j), f(k) + v(j)), 这个也就是这次动态规划的转移方程..

答案:

#include <cstdio>
#include <algorithm>

using namespace std;

int ti, m, ans;
int v[105], t[105], f[1005];
int i, j;
int main()
{
    scanf("%d%d", &ti, &m);
    for(i = 1; i <= m; ++i){
        scanf("%d%d", &t[i], &v[i]);
    }

    for(i = 1; i <= m; ++i)
        for(j = ti; j >= 0; --j)       //时间倒序, 保证每种草药采一次
            if(j + t[i] <= ti)         //如果采当前草药满足时间条件的话
                f[j + t[i]] = max(f[j + t[i]], f[j] + v[i]); // 试试看能不能更新当前时间点的最大值
    for(i = 0; i <= ti; ++i)
        ans = max(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}

1006

模拟..一个很简单的题, 主要就是字符数字转数字需要 - ‘0’

答案:

#include <cstdio>
#include <cstring>
using namespace std;

char s[105];
int i, j, tot, cnt, ans;
int main()
{
    while(scanf("%s", s + 1)){
        for(i = 1; i <= 11; ++i)
            if(s[i] != '-'){
                tot += (s[i] - '0') * (++cnt);
                tot = tot % 11;
            }
        if(tot == 10) ans = 'X';
        else ans = tot + '0';
        if(ans == s[13]) puts("Right");
        else{
            s[13] = ans;
            printf("%s\n", s + 1);
        }
    }
    return 0;
}

1007

我!居!然!没!有!思!路!, (╯‵□′)╯︵┻━┻, (╯‵□′)╯︵┻━┻

先抄答案, 具体思路过两天心情好了再看

黄学长答案:

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int m, n, k, l, d;
struct data{
    int pos, v;
    friend bool operator< (data a, data b){
        if(a.v == b.v) return a.pos < b.pos;
        return a.v > b.v;
    }
}r[1005], c[1005];
vector<int> ans1, ans2;

int main()
{
    scanf("%d%d%d%d%d", &m, &n, &k, &l, &d);
    for(int i = 1; i <= m; ++i)
        r[i].pos = i;
    for(int i = 1; i <= n; ++i)
        c[i].pos = i;
    for(int i = 1; i <= d; ++i){
        int x, y, p, q;
        scanf("%d%d%d%d", &x, &y, &p, &q);
        if(x == p) c[min(q,y)].v++;
        else r[min(x, p)].v++;
    }
    sort(r + 1, r + m + 1);
    sort(c + 1, c + n + 1);
    for(int i = 1; i <= k; ++i)
        ans1.push_back(r[i].pos);
    for(int i = 1; i <= l; ++i)
        ans2.push_back(c[i].pos);
    sort(ans1.begin(), ans1.end());
    sort(ans2.begin(), ans2.end());
    for(int i = 0; i < ans1.size(); ++i)
        printf("%d ", ans1[i]);
    puts("");
    for(int i = 0; i < ans2.size(); ++i)
        printf("%d ", ans2[i]);
    puts("");
    return 0;
}

1008

我会告诉你我的第一个思路是直接画邻接矩阵然后求路径矩阵吗..不过就是复杂度高了点, 写这个题可以很快, 不停重复矩阵运算就行.

后来看了黄学长的答案, 发现这个思路更好一些, 不需要邻接矩阵, 还是转成了一个dp问题.

假设f(i, j)是第i次传球后给j的方案数, 那么下一次传球就产生了两种方案:

f(i + 1, j + 1) += f(i, j)   //传给右边的人
f(i + 1, j - 1) += f(i, j)   //传给左边的人

根据上述方程遍历一遍就能得出来所有的f(i, j)值了, 答案也就出来了, 直接是f[m][1], 传m次, 传回自己的方案数

要注意的一点是, 上述式子里的 j + 1和 j - 1只是抽象的左右, 在这个环里面还要考虑到这个环关于n的周期性, 所以下方有一个名字为g的辅助函数, 用来达到上述转移方程的效果.

上答案:

#include <cstdio>
#include <algorithm>

using namespace std;
int m, n, i, j;
int f[35][35]; //前i次传球, 传给j的方案数
int g(int x){  //辅助函数, 表示一个圈的左右关系
    if(x < 1) return (x + n);
    else if(x > n) return (x - n);
    return x;
}
int main()
{
    scanf("%d%d", &n, &m);
    f[0][1] = 1;   //边界条件
    for(i = 0; i <= m; ++i)
        for(j = 1; j <= n; ++j){
            f[i + 1][g(j + 1)] += f[i][j];
            // f[i][j]  =>  f[i+1][j+1] 传给右边
            
            // f[i][j]  =>  f[i+1][j-1] 传给左边
            f[i + 1][g(j - 1)] += f[i][j];
        }
    printf("%d\n", f[m][1]); 
    return 0;
}