AtCoder Regular Contest #020
問題文
色は全部で $10$ 色あって,$1$ から $10$ の整数で表される.
一列に $N$ 個のセルがあって,$i$ 番目のセルは $A_i$ の色で塗られている.
各セルは,コスト $C$ で好きな色に塗り替えることができる.
縞模様にする最小コストを求める問題.
縞模様とは,全体でちょうど $2$ 色のみが使われていて,隣り合うセルは違う色であるようなものである.
奇数番目のセルの色と,偶数番目のセルの色を何にするかを全部試す.
$O(10^2 N)$.($10$ は色の数を意味する)
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int main(){
int i,j,k,l,m,n,c;
int in[1000];
int res, tmp;
scanf("%d%d",&n,&c);
res = n;
rep(i,n) scanf("%d",in+i), in[i]--;
rep(i,10) rep(j,10) if(i!=j){
tmp = 0;
for(k=0;k<n;k+=2) if(in[k]!=i) tmp++;
for(k=1;k<n;k+=2) if(in[k]!=j) tmp++;
if(tmp < res) res = tmp;
}
res *= c;
printf("%d\n",res);
return 0;
}
Current time: 2024年03月29日07時37分45秒
Last modified: 2014年03月30日00時16分55秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC020 ARC_B
トップページに戻る
Logged in as: unknown user (not login)