標題:
npsc2019_F. bb 與序列
[打印本頁]
作者:
葉桔良
時間:
2022-11-4 00:54
標題:
npsc2019_F. bb 與序列
本帖最後由 葉桔良 於 2022-11-4 21:15 編輯
F. bb 與序列
Problem ID: coloring
某天 bb 拿到了一個序列,這個序列裡面的數字有正有負也有可能有零,而 bb 想用紅、
綠、藍三種顏色幫這個序列上色。為了美觀,每個數字都必須被標上顏色,而且序列中任兩個
相鄰的數字必須要被標上不同的顏色。
由於 bb 喜歡綠色且討厭紅色,他覺得這個序列上色之後的價值是標上綠色的數字的總和
扣掉標上紅色的數字的總和。
請問在滿足上述的條件下,這個序列上色後價值可以變成多高呢?
Input
輸入的第一行有一個正整數 N,代表序列的長度。
第二行有 N 個以空格分開的整數 v1, v2, . . . vN,代表序列依序的數值。
• 1 ≤ N ≤ 106
• −1000 ≤ vi ≤ 1000
Output
輸出只有一行,代表上色之後這個序列的最高可能價值。
作者:
葉桔良
時間:
2022-11-4 19:26
#include <bits/stdc++.h>
using namespace std;
int num[105]={0};
int num1[105]={0};
int N[105]={0}; //0無 1綠 2藍 3紅
int sum=0;
int cmp( int a,int b){ //宣告以絕對值排序
return abs(a)>abs(b);
}
int main()
{
int n;//7
while(cin>>n){ //4 -6 10 3 -10 -1 5
for(int i=1;i<=n;i++){
cin>>num[i];
num1[i]=num[i]; //讓num1[]裡的值和num[]陣列一致
}
sort(num1+1,num1+n+2,cmp);// 10 -10 6 5 4 3 -1//從num1[1]到num1[n],以絕對值排序
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(num1[i]==num[j]){
if(num[j]>=0){//若為正值
if(N[j-1]!=1 && N[j+1]!=1) {
N[j]=1;
sum+=num[j];
}
else if(N[j-1]!=2 && N[j+1]!=2)
N[j]=2;
else{
N[j]=3;
sum-=num[j];
}
}
else{//若為負值
if(N[j-1]!=3 && N[j+1]!=3){
N[j]=3;
sum-=num[j];
}
else if(N[j-1]!=2 && N[j+1]!=2)
N[j]=2;
else{
N[j]=1;
sum+=num[j];
}
}
}
}
continue;
}
cout<<sum<<endl;
return 0;
}
}
複製代碼
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/)
Powered by Discuz! 7.2