Problem A Cut

题面

给你一个长度为$n$的序列，你每次可以将一个序列分割成两个连续的的子序列，分割的代价为原序列的总和。现在允许你在初始时将序列重新排列一次。问分割成$n$个长度为$1$的序列的最大总代价是多少？

题解

在从小到大排序后，显然答案为$$\sum_{i}^{n-1}a_i \times i + a_n \times (n-1)$$

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int n;
    long long ans=0;
    vector<int> vec;
    cin>>n;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        vec.push_back(t);
    }
    sort(vec.begin(),vec.end());
    for(int i=0;i<n;i++){
        ans+=vec[i]*(i+1); 
    }
    cout<<ans-vec[n-1]<<endl;
    return 0;
} 

Problem B 用水填坑

题面

现有一块$n \times m$的地，每块$1 \times 1$的地的高度为$h_{i,j}$，在$n \times m$的土地之外的土地高度均为$0$（即你可以认为最外圈无法积水）

现在下了一场足够大的雨，试求出这块地总共积了多少单位体积的水。

题解

首先假定这里涨了一场洪水所有的地方水涨到了与最高峰平齐的位置，然后退潮水向下下降，然后外流，直到流不动位置，此时统计即为答案。

代码

#include <iostream>
using namespace std;
const short MAXM=1005;
bool fuck;
int n,m;
long long ma[MAXM][MAXM],water[MAXM][MAXM],ans=0,bw; 
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ma[i][j];
            bw=max(ma[i][j],bw);
            ans-=ma[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        //Begin
        for(int j=1;j<=m;j++){
            water[i][j]=bw;
        }
    }
    do{
        fuck=false;
        for(int i=1;i<=n;i++){
            //Left
            for(int j=1;j<=m;j++){
                if(water[i][j-1]<water[i][j]&&water[i][j]!=max(water[i][j-1],ma[i][j])){
                    water[i][j]=max(water[i][j-1],ma[i][j]);
                    fuck=true;
                }
            }
            //Right
            for(int j=m;j>0;j--){
                if(water[i][j+1]<water[i][j]&&max(water[i][j+1],ma[i][j])!=water[i][j]){
                    water[i][j]=max(water[i][j+1],ma[i][j]);
                    fuck=true;
                }
            }
        }
        for(int i=1;i<=m;i++){
            //Up
            for(int j=1;j<=n;j++){
                if(water[j-1][i]<water[j][i]&&water[j][i]!=max(water[j-1][i],ma[j][i])){
                    water[j][i]=max(water[j-1][i],ma[j][i]);
                    fuck=true;
                }
            }
            //Down
            for(int j=n;j>0;j--){
                if(water[j+1][i]<water[j][i]&&water[j][i]!=max(water[j+1][i],ma[j][i])){
                    water[j][i]=max(water[j+1][i],ma[j][i]);
                    fuck=true;
                }
            }
        }
    }while(fuck);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans+=water[i][j];
        }
    }
    cout<<ans<<endl;
    return 0;
}

Problem C 序列

该题目为Codeforces 743E，以下为中文翻译。

题面

给定一个长度为$n$的序列，序列中的数字只由$[1,8]$这八个数字组成。要你找一个最长的子序列满足下面的两个条件：

• 子序列中每个数字的数目相差不超过$1$，即$|num_i-num_j| \leq 1(1 \leq i \leq j \leq 8),比如序列$[1,1,2,2]$不满足条件，因为$|num_8-num_1| =2 gt 1$
• 相同数字在子序列中要求连续，比如序列$[1,1,2,2,1,1]$不满足条件。

题解

设子序列中每个数字的数量至少为$len$，其中长度为$len+1$的为$k$个，则子序列长度为$$k \times (len+1)+(8−k) \times len$$，通过二分枚举$len$，然后用状压DP判断是否可行并得到最大的$k$，设数组$dp[n][(1<<8)−1]$，在$dp[i][s]$中，$s$ 的二进制串中，$1$表示那个数字已经出现了至少$len$次，反之亦然。$dp[i][s]$表示在前$i$位中，$s$的二进制串为$1$那位的那个数字已经出现了至少len次。

代码

#include <bits/stdc++.h>
using namespace std;
const short MAXN = 1010;
int n;
vector< int > g[10];
int a[MAXN], p[10], cur[10], dp[MAXN][1 << 8];
inline int check( int len ) {
    memset( cur, 0, sizeof( cur ) );
    memset( dp, -1, sizeof( dp ) );
    dp[0][0] = 0;
    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; j < ( 1 << 8 ); j++ ) {
            if ( dp[i][j] == -1 )
                continue;
            for ( int k = 1; k <= 8; k++ ) {
                if ( j & ( 1 << ( k - 1 ) ) )
                    continue;
                int x = cur[k] + len - 1;
                if ( x >= g[k].size() )
                    continue;
                dp[g[k][x]][j | ( 1 << ( k - 1 ) )] = max( dp[g[k][x]][j | ( 1 << ( k - 1 ) )], dp[i][j] );
                if ( ( ++x ) >= g[k].size() )
                    continue;
                dp[g[k][x]][j | ( 1 << ( k - 1 ) )] = max( dp[g[k][x]][j | ( 1 << ( k - 1 ) )], dp[i][j] + 1 );
            }
        }
        cur[a[i]]++;
    }
    int ans = -1;
    for ( int i = 1; i <= n; i++ )
        ans = max( ans, dp[i][( 1 << 8 ) - 1] );
    if ( ans == -1 )
        return -1;
    return ans * ( len + 1 ) + ( 8 - ans ) * len;
}
void Solve() {
    int l = 1, r = n / 8, mid;
    while ( l + 1 < r ) {
        mid = ( l + r ) >> 1;
        if ( check( mid ) != -1 )
            l = mid;
        else
            r = mid - 1;
    }
    int ans = max( check( l ), check( r ) );
    if ( ans == -1 ) {
        ans = 0;
        for ( int i = 1; i <= 8; i++ )
            if ( g[i].size() )
                ans++;
    }
    cout << ans << endl;
}
int main() {
    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i];
        g[a[i]].push_back( i );
    }
    Solve();
    return 0;
}

版权属于：来自星星的薇薇安

本文链接：https://www.starroad.top/archives/393.html

如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！