Loading... ## Problem A Cut ### 题面 给你一个长度为$n$的序列，你每次可以将一个序列分割成两个连续的的子序列，分割的代价为原序列的总和。现在允许你在初始时将序列重新排列一次。问分割成$n$个长度为$1$的序列的最大总代价是多少？ ### 题解 在从小到大排序后，显然答案为$$\sum_{i}^{n-1}a_i \times i + a_n \times (n-1)$$ ### 代码 ```cpp #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$（即你可以认为最外圈无法积水） 现在下了一场足够大的雨，试求出这块地总共积了多少单位体积的水。 ### 题解 首先假定~~这里涨了一场洪水~~所有的地方水涨到了与最高峰平齐的位置，然后~~退潮~~水向下下降，然后外流，直到流不动位置，此时统计即为答案。 ### 代码 ```cpp #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](http://codeforces.com/problemset/problem/743/E)，以下为中文翻译。 ### 题面 给定一个长度为$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次。 ### 代码 ```cpp #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; } ```<hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于：淡淡的路瑶</p><p class="content-copyright">本文链接：<a class="content-copyright" href="https://www.starroad.top/archives/393.html">https://www.starroad.top/archives/393.html</a></p><p class="content-copyright">如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！</p></blockquote> Last modification：July 19th, 2019 at 11:52 am © 允许规范转载 Support 如果您觉得我的文章有用，给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
