bzoj|【bzoj 1609】麻烦的聚餐
传送门~
解题思路 【bzoj|【bzoj 1609】麻烦的聚餐】f[i][j]表示到第i位最大号码为j的最小修改次数，正反分别跑依次就行了。
代码：
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int a[30005],b[30005];
int f[30005][4];
int n,ans=2147483640,mx=2147483640;
int main(){
scanf("%d",&n);
for(int i=1;
i<=n;
i++){
scanf("%d",&a[i]);
b[n-i+1]=a[i];
}for(int i=1;
i<=n;
i++)
for(int j=1;
j<=3;
j++){
f[i][j]=mx;
for(int k=j;
k>=1;
k--)
f[i][j]=min(f[i][j],f[i-1][k]);
if(j!=a[i]) f[i][j]++;
}
for(int i=1;
i<=3;
i++) ans=min(f[n][i],ans);
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=3;
j++){
f[i][j]=mx;
for(int k=j;
k>=1;
k--)
f[i][j]=min(f[i][j],f[i-1][k]);
if(j!=b[i]) f[i][j]++;
}
for(int i=1;
i<=3;
i++) ans=min(f[n][i],ans);
printf("%d",ans);
return 0;
} 推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长