ICPC Beijing 2017 J, Pangu and Stones
http://oj.daimayuan.top/course/8/problem/327
题意：有n堆石子，需要合并成一堆，但每次合并必须合并>=L且<=R堆，代价为总和，求最小代价。（n<=100)
题解：经典的石子合并是两两合并，而此处是多堆合并，直接枚举所有合并不现实，我们考虑多加一维状态，dp[i][j][k]表示将i->j合并成k堆的最小代价，则转移为dp[i][j][k]=min(dp[i][j][k],dp[i][mid][1]+dp[mid+1][j][k-1]);且当i->j数量满足题意时更新dp[i][j][1]。复杂度为O(n4).
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105,inf=1<<29;
int a[N],s[N],f[N][N][N],n,L,R;
void solve(){
for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++) f[i][j][k]=inf;
for(int d=0;d<=n-1;d++){
for(int l=1;l+d<=n;l++){
int r=l+d;
if(d==0){
f[l][r][1]=0;
}
else{
for(int k=2;k<=n;k++){
for(int m=l;m<r;m++){
f[l][r][k]=min(f[l][r][k],f[l][m][1]+f[m+1][r][k-1]);
}
if(k>=L&&k<=R) f[l][r][1]=min(f[l][r][1],f[l][r][k]);
}
f[l][r][1]+=s[r]-s[l-1];
}
}
}
if(f[1][n][1]>=inf){
cout<<0<<endl;
}
else cout<<f[1][n][1]<<endl;
}
signed main(){
// int T;cin>>T;
while(scanf("%d%d%d",&n,&L,&R)!=EOF){
solve();
}
}
ICPC Kunming 2020 C, Cities
http://oj.daimayuan.top/course/8/problem/328
题意:给定一个序列,你可以将一段相同数字的连续段全部改成另一个数字,问最少操作次数将其染为同一颜色.n<=5000且保证每种数字不会超过15个.
题解:我们先考虑上界,最多只需要n-1次操作即可完成染色,每次操作可视为将1个不同的相邻数减少1个(预处理将原本就相同的数删去),则能够使得操作数减少当且仅当一步操作可以消去2个"不相同",即中间改为和左右两端一致颜色时成立,那么我们可以考虑区间dp,每次转移只会找相同数作为中间值转移最优,令f[l][r]为将[l,r]染为同一色的能优化的步数,则初始化f[l][r]=f[l+1][r],转移为
f[l][r]=max(f[l][r],f[l+1][nex-1]+1+f[nex][r]);复杂度为O(15*n2);
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005;
int a[N],f[N][N];
vector<int> g[N];
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++) g[i].clear();
for(int i=1;i<=n;i++) cin>>a[i],g[a[i]].push_back(i);
for(int i=1;i<=n;i++){
f[i][i]=0;
}
for(int d=1;d<n;d++){
for(int l=1;l+d<=n;l++){
int r=l+d;
if(a[l]!=a[r])
f[l][r]=min(f[l+1][r]+1,f[l][r-1]+1);
else f[l][r]=min(f[l+1][r],f[l][r-1]);
for(auto it:g[a[r]]){
if(it<=r&&it>l){
f[l][r]=min(f[l][r],f[l][it]+f[it][r]);
}
}
}
}
cout<<f[1][n]<<endl;
// for(int i=1;i<=n;i++){
// for(int j=i;j<=n;j++){
// cout<<f[i][j]<<" ";
// }
// cout<<endl;
// }
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--)
solve();
}
ICPC CERC 2014 L, Outer space invaders
http://oj.daimayuan.top/course/8/problem/330
题意:略,,
题解:直接考虑比较抽象,由于其有两个维度,我们考虑将其放在一个二维坐标系下观察.
发现一次操作相当于在ti处画一条线段,将穿过该线的段全部删除,问最小代价.首先考查极端情况,由于距离我们最远的线段我们不得不花费D代价取消灭它,所以我们会在其上选一个L<=t<=R,用一条与其同高的线穿过它,同时区间会被划分为左右两个互不相关的子问题,此时可以考虑区间dp(用记忆化搜索实现).
dp[l][r]表示从t轴的l->r最少花费多少可以消除所有全部位于其上的线段,则f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+mx),其中k位于[l,r]内最高的线段中.复杂度为O(n3).
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int a[N],n,dp[N][N],d[N],b[N];
int solve(int l,int r){
if(l>r) return 0;
if(dp[l][r]!=-1) return dp[l][r];
int &ans=dp[l][r];
ans=(1<<29);
int mx=-1,mxp=-1;
for(int i=1;i<=n;i++){
if(a[i]>=l&&b[i]<=r)
if(d[i]>mx) mx=d[i],mxp=i;
}
if(mx==-1){
ans=0;
return ans;
}
for(int i=a[mxp];i<=b[mxp];i++){
ans=min(ans,solve(l,i-1)+solve(i+1,r));
}
ans=ans+mx;
return ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--){
cin>>n;
vector<int> v;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>d[i],v.push_back(a[i]),v.push_back(b[i]);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int m=v.size();
for(int i=1;i<=n;i++){
a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
b[i]=lower_bound(v.begin(),v.end(),b[i])-v.begin()+1;
}
for(int i=1;i<=m;i++){
for(int j=i;j<=m;j++) dp[i][j]=-1;
}
cout<<solve(1,m)<<endl;
}
}