南外Day7

A&B&C&E 100

水

D 100

排序贪心，
计算得到i,j先后顺序影响到的是a[i]*b[j]

//D 0-None
#include<bits/stdc++.h>
#define int long long
#define MX 100005
using namespace std;
struct nd{int a,b;}x[MX];
bool cmp(nd xx,nd yy){return xx.a*yy.b<xx.b*yy.a;}
int n,ans,mod=31536000ll;
signed main(){
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i].a>>x[i].b;
    sort(x+1,x+1+n,cmp);
    for(int i=1;i<=n;i++){
        ans=(ans*(x[i].b+1)+x[i].a)%mod;
    }
    cout<<ans;
    return 0;
}

F 100

还算简单的区间DP
我这边复杂度似乎出了点问题但还是过了的

#include<bits/stdc++.h>
using namespace std;
int n,f[105][105][30],f2[105][105],a[105],b[105],nxt[105],lst[30];
int o(char CRH){return int(CRH-&#039;a&#039;+1);}string s;
int sol(int l,int r,int p){
    if(f[l][r][p]>-1) return f[l][r][p];
    if(l>r){return f[l][r][p]=0;}
    if(l==r){return f[l][r][p]=(p==b[l]?0:1);}
    int ans=r-l+1;
    for(int i=l;i<=r;i++){
        int nw=i;
        while(nw<=r){
            if(b[i]==p)
                ans=min(ans,sol(l,i-1,p)+sol(i+1,nw-1,p)+sol(nw+1,r,p));
            else
                ans=min(ans,sol(l,i-1,p)+sol(i,nw,b[i])+sol(nw+1,r,p)+1);
            nw=nxt[nw];
        }
    }
    return f[l][r][p]=ans;
}
int sol2(int l,int r){
    if(f2[l][r]>-1) return f2[l][r];
    if(l>r){return f2[l][r]=0;}
    if(l==r){return f2[l][r]=(a[l]==b[l]?0:1);}
    int ans=f[l][r][0];
    for(int i=l;i<=r;i++)
    if(a[i]==b[i])
        ans=min(ans,sol2(l,i-1)+sol2(i+1,r));
    return f2[l][r]=ans;
}
int main(){
    cin.tie(0);cout.tie(0);
    cin>>s;n=s.size();for(int i=0;i<n;i++){a[i+1]=o(s[i]);}
    cin>>s;n=s.size();for(int i=0;i<n;i++){b[i+1]=o(s[i]);}
    memset(f,-1,sizeof(f));memset(f2,-1,sizeof(f2));
    memset(nxt,0x3f,sizeof(nxt));
    for(int i=1;i<=n;i++){
        nxt[lst[b[i]]]=i;
        lst[b[i]]=i;
    }
    for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){
        for(int k=0;k<=26;k++)
            sol(i,j,k);
    }}
    sol2(1,n);
    cout<<f2[1][n]<<endl;
    return 0;
}

G&H

¿