2023-5-9.md

Note

• 补题（上周六的debug杯）
• 1005 选数游戏：大意：对于一个由n个整数构成的数列a1​,a2​,...,an，​按序取出相邻下标小于等于k的元素，目标是输出子序列所有元素的最大和。
• 思路：dp，状态转换方程：sum[i]=max(sum[i],max(sum[i-k],sum[i-k+1],...sum[i-1])+a[i])
• 1003 给你一张有n个顶点和m条边的无向图， 你要判断它是不是一棵树。
• 思路：邻接矩阵，先用边点先判断，再使用bfs或dfs查找是否联通，注意需要将vis和a数组更新（or 清零）。

Code

// 1005
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll sum[1010];
ll a[1010];
void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = a[i];
    }
    ll ans = 0;
    for (int i = 2; i <= n; i++)
        for (int j = max(0, i - k); j < i; j++)
        {
            sum[i] = max(sum[i], sum[j] + a[i]);
            ans = max(ans, sum[i]);
        }
    cout << ans << endl;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt;
    cin >> tt;
    while (tt--)
        solve();
    return 0;
}

// 1003
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int a[2010][2010];
int vis[2010];
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        vis[i] = 0;
        for (int j = 1; j <= n; j++)
            a[i][j] = a[j][i] = 0;
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        a[u][v] = a[v][u] = 1;
    }
    if (m != n - 1)
    {
        cout << "no\n";
        return;
    }
    queue<int> q({1});
    vis[1] = 1;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        for (int i = 1; i <= n; i++)
        {
            if (vis[i] || a[t][i] == 0)
                continue;
            q.push(i);
            vis[i] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            cout << "no\n";
            return;
        }
    }
    cout << "yes\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt;
    cin >> tt;
    while (tt--)
        solve();
    return 0;
}