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;
}
0 条评论