4-19 补题 第四次训练

A.Dima and Salad

题意：有n个物体，每个物体有两个参数，a，b，输入k，从n个物品中选出若干个，要求在满足
\displaystyle \sum^{m}_{j=1}{{a[j]}} = k*\displaystyle \sum^{m}_{j=1}{{b[j]}}的基础上，使得a[j]的和最大。
对公式变形，使b[i] = k*b[i]-a[i]，问题转变成使b[i]之和为0的条件下，a[i]的和最大。但是b[i]有正有负，所以维护两个数组f[]，g[]，f[i]表示所有正的b中，和为i时a的最大和，g[i]表示所有负的b中，和为-i时a的最大和。最后统计答案时，找到max(f[i]+g[i])即可。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
int a[105],b[105];
int f[maxn+10],g[maxn+10];
int main(){
    int n,k,ans = 0;
    scanf ("%d %d",&n,&k);
    for (int i=1;i<=n;i++)
        scanf ("%d",&a[i]);
    for (int i=1;i<=n;i++){
        scanf ("%d",&b[i]);
        b[i] *= k;  b[i] -= a[i];
    }
    for (int i=1;i<=n;i++){
        if (b[i]>0){
            for (int j=maxn;j>=b[i];j--)    if (f[j-b[i]] || j-b[i]==0)
                f[j] = max(f[j],f[j-b[i]]+a[i]);
        }else{
            for (int j=maxn;j>=-b[i];j--)   if (g[j+b[i]] || j+b[i]==0)
                g[j] = max(g[j],g[j+b[i]]+a[i]);
        }
    }
    ans = max (ans,f[0]+g[0]);
    for (int i=1;i<=maxn;i++)
        ans = max(ans,(f[i]&&g[i])?f[i]+g[i]:0);
    printf ("%d",ans?ans:-1);
    return 0;
}

H.Palindrome

题意：给一字符串s，1<=|s|<=5e4，求这个字符串的最大回文子序列，当子序列长度超过100时，只输出100个，否则全部输出。s由小写字母构成。
考虑到s只有小写字母，且只求长度<=100的子序列，所以只需考虑s的前2600个字符即可。然后区间dp求解。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 5e4+6;
char s[maxn];
char ans[maxn];
int tot;
int dp[2605][2605];
int main(){
    scanf ("%s",s+1);
    int len = min((int)strlen(s+1),2600);
    for (int i=1;i<=len;i++)    dp[i][i] = 1;
    for (int i=1;i<=len;i++)   for (int j=i-1;j>=1;j--){
        dp[j][i] = max(dp[j][i-1],dp[j+1][i]);
        if (s[i]==s[j]) dp[j][i] = max(dp[j][i],dp[j+1][i-1]+2);
    }
    int begin = 1, end = len;  tot = 0;
    while (begin<end){
        if (dp[begin][end]==dp[begin+1][end]){
            begin++;
            continue;
        }else if (dp[begin][end]==dp[begin][end-1]){
            end--;
            continue;
        }else{
            ans[++tot] = s[end];
            begin++,end--;
        }
    }
    int lengt = 2*tot+(begin==end);
    if (lengt<=100){
        for (int i=1;i<=tot;i++)    putchar(ans[i]);
        if (begin==end) putchar(s[begin]);
        for (int j=tot;j>=1;j--)    putchar(ans[j]);
    }else{
        for (int i=1;i<=50;i++)    putchar(ans[i]);
        for (int j=50;j>=1;j--)    putchar(ans[j]);
    }
    return 0;
}