目录

1004.Link with Equilateral Triangle(签到题)

1006.BIT Subway(模拟)

1007.Climb Stairs

1001.Link with Bracket Sequence II(区间dp)

1004.Link with Equilateral Triangle(签到题)

直接全部输出NO

1006.BIT Subway(模拟)

思路:直接模拟即可

#include
using namespace std;
double a[100005];
void solve()
{
    int n;
    double sum=0,ans1=0,ans2=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&a[i]);
        sum+=a[i];
        if(ans2<100.0)
            ans2+=a[i];
        else if(ans2<200.0)
            ans2+=a[i]*0.8;
        else
            ans2+=a[i]*0.5;
    }
    if(sum>100.0)
    {
        ans1+=100.0;
        sum-=100.0;
        if(sum>100.0/0.8)
        {
            ans1+=100.0;
            sum-=100.0/0.8;
            sum*=0.5;
            ans1+=sum;
        } 
        else
            ans1+=sum*0.8;
    }
    else
        ans1+=sum;
    printf("%.3lf %.3lf\n",ans1,ans2);
    return ;
}
signed main()
{
    int t;
    scanf("%d",&t);
    while(t--)
       solve();
    return 0;
}

1007.Climb Stairs

题意:n个怪兽,每个怪兽血量a[i],你有a[0]攻击力,每次杀死怪兽攻击力上升他们的血量,每次我们可以从当前位置向下跳跃到后k个位置,或者向上跳跃一层.当然,已经到过的楼层不能再去.问是否可以杀完所有怪兽.

思路:我们根据题意可以推测出最优的打怪方法就是跳跃到一层之后直接把下面没有杀死的怪物杀死然后在跳跃到之后的某一层,再下降把没有杀死的怪物杀死.

那么知道这个策略之后,问题就在于我们如何判断保证从当前起点跳跃到之后的某个点后,可以下来把上一个落脚点和当前点之间的怪物全部杀死.首先知道,在能确保上述条件的情况下,我们肯定要能跳就跳,这样再面对下一次杀怪时可以拥有最大的攻击力.然后就是对于每次跳跃的抉择问题.

我们直接从当前点开始往后遍历,记录跳到这个点需要至少多少体力,例如我们一开始攻击力atk为3连续3只怪物生命为7 4 3的时候,我们往后遍历,打败第一只怪兽所需要的攻击力就是min(atk-7,7),即为7,记录下为f[1].那么打败第二只怪兽的战斗力就是f[2]=max(f[1]-4,4)=4.第三只的则需要的战斗力是max(f[2]-3,3)=3;这里的取max的意义就是我在保证能打败这个怪兽的情况下(即为>=当前怪兽攻击力),和打败这一只怪兽之后再去打败上一只怪兽(f[i-1]-当前怪兽攻击力).两者取max,就可以贪心的找到最优解.

#include
#define int long long
using namespace std;
const int N =1e5+10,mod=998244353;
int a[N],vis[N];
void solve()
{
    memset(vis,0,sizeof vis);
    int n,k;
    scanf("%lld%lld%lld",&n,&a[0],&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    int l=0,maxx,st=a[0];
    while(l<=n)
    {
        int f=0;
        vis[l]=1;
        maxx=0;
        for(int i=l+1;i<=n&&i-l<=k;i++)
        {
            maxx=max(a[i],maxx-a[i]);
            if(st>=maxx)
            {
                f=1;
                for(int j=l+1;j<=i;j++)
                    st+=a[j],vis[j]=1;
                l=i;
                break;
            }
        }
        if(f==0)
            break;
    }
    for(int i=0;i<=n;i++)
    {
        if(vis[i]==0)
        {
            printf("NO\n");
            return ;
        }
    }
    printf("YES\n");
    return ;
}
signed main()
{
    int t;
    scanf("%lld",&t);
    while(t--)
       solve();
    return 0;
}

1001.Link with Bracket Sequence II(区间dp)

题意:给你一个括号序列问有多少种匹配方式.
f[l][r]表示区间[l,r]内的合法子序列个数
g[l][r]表示匹配区间内所有括号进行匹配之后的方案数量
我们根据题意可知a[l]和a[r]可以得出四种情况,此四种情况
只能得出f的状态转移方程:
1.a[l]==a[r]&&a[l]==0
    f[l][r]=g[l+1][r-1]*m
2.a[l]==0&&a[r]!=0
    f[l][r]=g[l+1][r-1]*1
3.a[l]!=0&&a[r]==0
    f[l][r]=g[l+1][r-1]*1
4.a[l]+a[r]==0
    f[l][r]=g[l+1][r-1]*1
其余情况无法转移了
这里可以由f的状态转移得到g的状态
我们就可以把区间分成两段,枚举有意义的中点,来进行区间dp
计算g[l][r]的值,状态转移方程是为:
    g[l][r]+=g[l][k-1]*f[k][r];(此处的k是枚举的中点)
此处的转移方程意为把所有能匹配的分界点和左端点进行匹配,匹配成功后计算方案的的方式就是用前半段已经匹配好的方案数,和后面有多少种合法子序列进行匹配.如果是两段的方案数进行匹配就会计算重复,因为可能分界点在前方的时候已经把分界点在后方的情况枚举了.如果是两段的子序列数匹配也不行,没有漏统计了很多方案,用g[l][r]+=g[l][k-1]*f[k][r]就做到了不重不漏.

#include
#define int long long
using namespace std;
const int N =5e2+10,mod=1e9+7;
int f[N][N],g[N][N],a[N];
void solve()
{ 
    int n,m;
    memset(f,0,sizeof f);
    memset(g,0,sizeof g);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    if(n&1)
    {
        printf("0\n");
        return ;
    }
    for(int i=0;i<=n;i++)
        g[i+1][i]=1;
    for(int len=2;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            if(a[l]>=0&&a[r]<=0)
            {
                if(a[l]==a[r]&&a[l]==0)
                    f[l][r]=g[l+1][r-1]*m%mod;
                else if(a[l]==0||a[r]==0)
                    f[l][r]=g[l+1][r-1]%mod;
                else if(a[l]+a[r]==0)
                    f[l][r]=g[l+1][r-1]%mod; 
                else
                    f[l][r]=0;
            }
            for(int mid=l;mid<=n;mid+=2)
                g[l][r]=(g[l][r]+g[l][mid-1]*f[mid][r]%mod)%mod;
        }
    }
    printf("%lld\n",g[1][n]);
    return;
}
 
signed main()
{
    int t;
    scanf("%lld",&t);
    while(t--)
       solve();
    return 0;
}