牛客寒假4到6补题

标签：10 题意 int void 牛客 寒假 补题

牛客寒假4：

F：来点每日一题

题意：给定一个长度为 n 的数组，任意选6个数，6个数得分为 ((a-b) * c - d) * e - f，问最大能得到多少分 解：n*n的dp，暴力枚举每一个数字 v[i]，f[i]表示以第 i 个位置结尾的得分最大是多少  

void solve() {
    int n;
    cin >> n;
    vector<int> v(n+10) , f(n+10);
    for(int i=1;i<=n;i++) cin >> v[i];
    for(int i=1;i<=n;i++) {
        vector<int> minn(10 , INF), maxx(10 , -INF);
        f[i]=max(f[i],f[i-1]);
        for(int j=i;j<=n;j++) {
            for(int k=5;k>=1;k--) {
                for(int p : {minn[k - 1], maxx[k - 1]}) {
                    if(abs(p)<INF) {
                        if(k&1) p-=v[j];
                        else p*=v[j];
                        minn[k]=min(minn[k],p);
                        maxx[k]=max(maxx[k],p);
                    }
                }
            }
            minn[0]=min(minn[0],v[j]);
            maxx[0]=max(maxx[0],v[j]);
            f[j]=max(f[j],f[i-1]+maxx[5]);
        }
    }
    cout << f[n] << endl;
}

View Code

 

牛客寒假5： F：soyorin的数组操作（hard） 题意：有一个长度为n的数组，每次可以选择一个不大于n的偶数k，使得ai(1<=i<=k) 加上 i 。问最少需要操作多少步，可以使得数组非降序排列 解法：最开始写复杂了，想到二分去了，过了80%。 但是正解手画一下就知道了。 在有解的情况下，答案就是 Ai-Ai+1 的最大值，因为相邻两数每次操作只减小1差距，所以在有解的情况下，答案就是两相邻数最小需要达到非降序的操作次数最大值。

void solve() {
    int n;
    cin >> n;
    vector<int> v(n+10);
    for(int i=0;i<n;i++) cin >> v[i];
    int ans=0,cnt=0;
    for(int i=n-2;i>=0;i--) {
        if(n&1) {
            if(v[i+1]+cnt<v[i]) {
                cout << -1 << endl;
                return ;
            }
            if((i+1)%2==0) cnt+=(v[i+1]+cnt-v[i])/(i+1);
        }
        ans = max(ans, v[i]-v[i+1]);
    }
    cout << ans << endl;
}

View Code

 

K：soyorin的通知

题意：A想要将一条消息传给n个人。有两种操作：要么将消息单独传给一个人，花费p；要么花费 a 的代价将消息传给b个人。

问：将消息传给n个人最少需要多少代价。

解：将问题转换为完全背包看即可，对于代价和体积，题目已经给了，只是在传的时候要保证当前这个人已经知道了消息，即保证第一个人一定是花费p，后面的完全背包跑即可。

int f[1010],v[1010],w[1010];

void solve() {
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> v[i] >> w[i] , f[i]=INF;
    f[1]=k;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) f[j]=min({j*k , f[j] , f[max(1ll,j-w[i])]+v[i]});
    }
    cout << min(f[n],n*k) << endl;
}

View Code

 

 

 

 

标签：10,题意,int,void,牛客,寒假,补题
From： https://www.cnblogs.com/lzywakaka/p/18033035