【牛客Wannafly挑战赛12】 题解

传送门：https://www.nowcoder.com/acm/contest/79#question

说是比赛题解，其实我只会前三题；

后面的一定补

T1

题意，在一个长度为n的时间内，问如何选择存款期限，使得收益最大。

dp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define fi first
#define se second
double r[5];
double dp[30];
double ll(int n,int id,double a)
{
    double t=1.0;
    for(int i=1;i<=n;i++)
    {
        t=t*(1+r[id]);
    }
    return t*a;
}
int main(){
    
    int n;
    scanf("%d%lf%lf%lf%lf",&n,&r[1],&r[2],&r[3],&r[4]);
    memset(dp,0,sizeof(dp));
    dp[0]=1.0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=4;j++)
        {
            int nian=(j==4)?5:j;
            if(i>=nian)
            {
                dp[i]=max(ll(nian,j,dp[i-nian]),dp[i]);
            }
        }
    }
    printf("%.5lf
",dp[n]);

    return 0;
}

T2

利用前缀和即可；

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
typedef long long ll;
using namespace std;

const int maxn = 1000009;
ll a[maxn],b[maxn];
ll n,m;
bool cmp(ll a,ll b)
{
    return a > b;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&b[i]);
    }
    a[0]=0,b[0]=0;
    sort(a+1,a+1+n);
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        a[i]+=a[i-1];
        b[i]+=b[i-1];
    }

    ll ans = 0;
    ll ff=0;
    for(int i=1;i<=n; i++)
    {
        if(i%3==0)
            ff+=m;
        ll tmp = b[i]-a[i]+ff;
        if(tmp>ans)ans=tmp;
    }
    printf("%lld
",ans);
    return 0;
}

T3

题意：操作一个只含a，b的字符串，问能最少删去字母个数，使得在最后的字符串中，相邻不同的个数少于m个；

思路：dp；这题关键就是把（且新的字符串的首字母必须是'a'）这句话发挥得淋漓尽致，这也规定了答案字符串中，必须是一块a，一块b，一块a……

所以，如果 j 是偶数，表示后面就要接a，如果 j 是奇数，必须要有b才行； 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#define pb push_back
typedef long long ll;
using namespace std;

const int maxn = 1000009;
ll dp[maxn][20];
string s1;
int n,m;
int main(){
    cin>>n>>m>>s1;
    s1="*"+s1;
    memset(dp,0,sizeof(dp));
    int flag=1;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=m; j++)
        {
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
        }
        for(int j=0; j<=m; j++)
        {
            if(((j&1)&&s1[i]=='b')||(((j&1)==0)&&s1[i]=='a'))
            {
                if(j!=0)dp[i][j]=max(dp[i][j], dp[i-1][j-1]+1);
                dp[i][j]=max(dp[i][j], dp[i-1][j]+1);
            }
        }
        if(s1[i]=='a')flag=0;        //最后尽然把全b的情况忘记了
    }
    ll ans = 0;
    for(int i=0; i<=m; i++)
    {
        ans=max(ans, dp[n][i]);
    }
    if(flag)cout<<0<<endl;
    else cout<<ans<<endl;
    return 0;
}