G - Lighting System Design UVA - 11400

题意

有n种灯，每种灯有相对应的额定电压v和电源价格k，每种灯需要l个，每个c元。为了节省钱，可以用高电压的灯代替低电压的灯。求最小花费。

题解

首先按电压排序，这样可以方便替换电灯。再预处理灯泡个数的前缀和。dp[i]表示从1到i种灯安装好最少的花费。转移方程为dp[i] = min(dp[i],dp[j - 1] + (pre[i] - pre[i - 1] * c + k)。表示当前j到i类的灯泡替换为第i类灯泡的花费,再不断更新答案。

#include <bits/stdc++.h>
using namespace std;
int n,dp[1010],pre[1010];
struct cate
{
    int v,k,c,l;
}cat[1010];
bool cmp(struct cate x,struct cate y)
{
    return x.v < y.v;
}
int main()
{
    while(scanf("%d",&n) && n)
    {
        for(int i = 1;i <= n;i++) scanf("%d %d %d %d",&cat[i].v,&cat[i].k,&cat[i].c,&cat[i].l);
        sort(cat + 1,cat + 1 + n,cmp);
        pre[1] = cat[1].l;
        for(int i = 2;i <= n;i++)    pre[i] = pre[i - 1] + cat[i].l;
        for(int i = 1;i <= n;i++)
        {
            dp[i] = 1e9;
            for(int j = 1;j <= i;j++)
            {
                dp[i] = min(dp[i],dp[j - 1] + (pre[i] - pre[j - 1]) * cat[i].c + cat[i].k);
            }
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

H - Partitioning by Palindromes UVA - 11584

题意

求一个字符串种的最小回文串个数

题解

dp[i]表示前i个字符中的最小回文串个数。如果第i个字符加入后j到i组成回文串，那么更新答案dp[i] = min(dp[i],dp[j - 1] + 1)。

#include <bits/stdc++.h>
using namespace std;
int T,dp[1010];
char str[1010];
bool ok(int l,int r)
{
    for(int i = l;i <= r;i++)
    {
        if(str[i] != str[r - (i - l)]) return false;
    }
    return true;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",str);
        int n = strlen(str);
        for(int i = 0;i < n;i++)
        {
            dp[i] = dp[i - 1] + 1;
            for(int j = 0;j < i;j++)
            {
                if(ok(j,i)) dp[i] = min(dp[i],dp[j - 1] + 1);
            }
        }
        printf("%d\n",dp[n - 1]);
    }
    return 0;
}