url: https://www.luogu.com.cn/problem/CF149D

tag:
搜索，记忆化搜索，区间DP

思路：
使用 f[l][r][i][j] 表示区间l和r之间l为i色，r为j色时的染色方案数。有两种情况，当 l 和 r 配对时，可以由 l + 1 到 r - 1更新过来。如果不配对，由 l 到 第一个配对的括号这段区间和由那个括号后面的括号到 r 这段区间的方案数相乘。注意如果相邻的括号都有染色且颜色一样需要跳过。初始化是当 l + 1 == r 时，此时区间只有两个括号，对应的四个情况都只有一种方案。最后dfs之后将所有可能的答案相加并取模，然后输出即可。

代码：

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <stack>  
using namespace std;  
const int N = 800;  
const int mod = 1000000007;  
char s[N];  
stack<int> stk;  
int rightt[N];  
int f[N][N][5][5];  
void dfs(int l, int r)  
{  
    if (l + 1 == r)  
    {  
        f[l][r][0][1] = f[l][r][0][2] = f[l][r][1][0] = f[l][r][2][0] = 1;  
        return;  
    }  
    if (r == rightt[l])  
    {  
        dfs(l + 1, r - 1);  
        for (int i = 0; i <= 2; i ++)  
            for (int j = 0; j <= 2; j ++)  
            {  
                if (j != 1) f[l][r][0][1] += f[l + 1][r - 1][i][j], f[l][r][0][1] %= mod;  
                if (j != 2) f[l][r][0][2] += f[l + 1][r - 1][i][j], f[l][r][0][2] %= mod;  
                if (i != 1) f[l][r][1][0] += f[l + 1][r - 1][i][j], f[l][r][1][0] %= mod;  
                if (i != 2) f[l][r][2][0] += f[l + 1][r - 1][i][j], f[l][r][2][0] %= mod;  
            }  
    }  
    else  
    {  
        dfs(l, rightt[l]), dfs(rightt[l] + 1, r);  
        for (int i = 0; i <= 2; i ++)  
            for (int j = 0; j <= 2; j ++)  
                for (int p = 0; p <= 2; p ++)  
                    for (int q= 0; q <= 2; q ++)  
                    {  
                        if (j == 1 && p == 1 || j == 2 && p == 2) continue;  
                        f[l][r][i][q] += (f[l][rightt[l]][i][j] * f[rightt[l] + 1][r][p][q] % mod);  
                        f[l][r][i][q] %= mod;  
                    }  
    }  
}  
int main() {  
    scanf("%s", s + 1);  
    int n = strlen(s + 1);  
    for (int i = 1; i <= n; i++)  
    {  
        if (s[i] == '(') stk.push(i);  
        else  
        {  
            rightt[i] = stk.top();  
            rightt[stk.top()] = i;  
            stk.pop();  
        }  
    }  
    dfs(1, n);  
    int res = 0;  
    for (int i = 0; i <= 2; i ++)  
        for (int j = 0; j <= 2; j ++)  
            res += f[1][n][i][j], res %= mod;  
    cout << res << endl;  
    return 0;  
}

问题描述

小R有nn部电脑，每部电脑的电池容量分别为aiai​。她可以使用两种不同的充电方式来给电脑充电：

1. 普通充电：每单位时间为电脑充电xx单位的电量。
2. 闪充：每单位时间为电脑充电4x4x单位的电量。

现在，所有电脑的电量都为零。小R希望使用闪充给所有电脑充满电，计算她需要的总充电时间。请保留结果的小数点后两位。

测试样例

样例1：

输入：n = 4 ,x = 1 ,a = [2, 3, 4, 5]
输出：'3.50'

样例2：

输入：n = 3 ,x = 2 ,a = [4, 6, 8]
输出：'2.25'

样例3：

输入：n = 2 ,x = 1 ,a = [10, 5]
输出：'3.75'

代码：

string solution(int n, int x, vector<int> a) {
    int res = 0;
    for (int i = 0; i < n; i ++) res += a[i];
    double ans = 1.0 * res / (x * 4); 
    ostringstream oss;
    oss << fixed << setprecision(2) << ans;
    return oss.str();
}

解释：

1. 返回值问题：使用 ostringstream 将浮点数格式化为保留两位小数的字符串，并返回该字符串。
2. 浮点数格式化：使用 iomanip 库中的 fixed 和 setprecision 来格式化浮点数。

url: https://www.luogu.com.cn/problem/P1453

tag:
动态规划，图论，基环树，树形DP

思路：
基环树是一种特殊的图结构，可以看作是在一棵树的基础上加入一条额外的边，从而使图中恰好出现一个环，也称作单环图或唯一环图（unicyclic graph）。其主要特点包括：

1. 连通性：基环树是连通图，任意两个顶点之间都有路径相连。
2. 唯一的环：整个图中仅存在一个简单环，其他部分均保持树的结构（即无环）。
3. 分解思想：可以将基环树看作由一个环和附着在环上各个顶点上的若干棵树构成。对于很多算法（例如树形 DP），通常先对环进行特殊处理（比如“断环”），再处理附着的树结构。

这种结构在算法竞赛中经常出现，处理时通常需要先找出环，然后考虑两种或多种情况（例如环上某些节点选或不选），从而在保证整体方案最优的前提下完成状态转移和求解。

这道题目其实和求树的最小覆盖问题类似，我们用 f[u][0/1] 表示节点u为根且选或者不选时的总共人流量。只是因为有基环树，所以需要先断边，然后分别用那一边的两个点为根且不选（方便另外一个点可选）时各跑一遍dfs，求答案，最后两个答案求一个最大值并乘上k，注意，对于不同的情况来说需要先将f数组清空（因为可选的点不同了）。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N * 2], ne[N * 2], idx;
int p[N];
bool st[N];
double k;
int n, s1, s2, flag;
int f[N][2];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dfs1(int u, int fa)
{
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if (v == fa) continue;
        if (st[v])
        {
            s1 = u, s2 = v;
            flag = true;
            return;
        }
        dfs1(v, u);
        if (flag) return ;
    }
    st[u] = 0;
}
void dfs2(int u, int fa)
{
    f[u][1] = p[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if (v == fa) continue;
        if ((u == s1 && v == s2) || (u == s2 && v == s1)) continue;
        dfs2(v, u);
        f[u][1] += f[v][0];
        f[u][0] += max(f[v][0], f[v][1]);
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> p[i];
    int a, b;
    for (int i = 0; i < n; i ++)
    {
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    cin >> k;
    dfs1(0, 0);
    dfs2(s1, s1);
    int res1 = f[s1][0];
    memset(f, 0, sizeof f);
    dfs2(s2, s2);
    int res2 = f[s2][0];
    printf("%.1f", max(res1, res2) * k);
    return 0;
}

昨天将一些没有用的可以卖的vps卖了。
今天将原来放在旧主机上的一个服务迁移到了现在的服务器上面。
racknerd上面的服务器我估计不好出，就到时候不续费就好。
现在相当于将每年的服务器成本降低了，太好了。

url: https://www.luogu.com.cn/problem/P1272

tag:
动态规划，树形DP

思路：
简单的树形DP和背包结合。令 f[u][j] 表示以u节点为根的子树在需要取出j个节点时最少需要断的边。最后在输出答案的时候在所有节点中选择一个答案最小的，注意选择其他节点为根节点时需要断去父节点和其之间的一条边。最后输出答案即可。

代码：

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
const int N = 200;  
int h[N], e[N * 2], ne[N * 2], idx;  
int s[N];  
int n, p;  
int f[N][N];  
void add(int a, int b)  
{  
    e[idx] = b;  
    ne[idx] = h[a];  
    h[a] = idx ++;  
}  
void dfs(int u, int fa)  
{  
    s[u] = 1;  
    f[u][1] = 0;  
    for (int i = h[u]; ~i; i = ne[i])  
    {  
        int v = e[i];  
        if (v == fa) continue;  
        dfs(v, u);  
        s[u] += s[v];  
        for (int j = min(s[u], p); j >= 0; j --)  
        {  
            f[u][j] += 1;  
            for (int k = 0; k <= min(j, s[v]); k++)  
                f[u][j] = min(f[u][j], f[u][j - k] + f[v][k]);  
        }  
    }  
}  
int main()  
{  
    memset(h, -1, sizeof h);  
    memset(f, 0x3f, sizeof f);  
    cin >> n >> p;  
    for (int i = 0; i < n - 1; i ++)  
    {  
        int a, b;  
        cin >> a >> b;  
        add(a, b), add(b, a);  
    }  
    dfs(1, 0);  
    int res = f[1][p];  
    for (int i = 2; i <= n; i ++) res = min(res, f[i][p] + 1);  
    cout << res << endl;  
    return 0;  
}