Board logo

標題: 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

  1. #include <bits/stdc++.h>      
  2. using namespace std;      
  3. int num[105]={0};
  4. int num1[105]={0};
  5. int N[105]={0}; //0無 1綠 2藍 3紅
  6. int sum=0;
  7. int cmp( int a,int b){        //宣告以絕對值排序
  8.      return abs(a)>abs(b);               
  9. }      
  10. int main()      
  11. {      
  12.     int n;//7      
  13.     while(cin>>n){        //4 -6 10 3 -10 -1 5
  14.       for(int i=1;i<=n;i++){
  15.               cin>>num[i];
  16.                 num1[i]=num[i]; //讓num1[]裡的值和num[]陣列一致         
  17.                 }
  18.           sort(num1+1,num1+n+2,cmp);// 10 -10 6 5 4 3 -1//從num1[1]到num1[n],以絕對值排序
  19.    
  20.                 for(int i=1;i<=n;i++){
  21.                     for(int j=1;j<=n;j++){
  22.                             if(num1[i]==num[j]){
  23.                                     if(num[j]>=0){//若為正值
  24.                                             if(N[j-1]!=1 && N[j+1]!=1) {
  25.                                                     N[j]=1;      
  26.                                                         sum+=num[j];
  27.                                             }
  28.                                             else if(N[j-1]!=2 && N[j+1]!=2)
  29.                                                 N[j]=2;
  30.                                             else{
  31.                                                     N[j]=3;
  32.                                                 sum-=num[j];                                          
  33.                                                 }                              
  34.                                         }
  35.                                         else{//若為負值
  36.                                             if(N[j-1]!=3 && N[j+1]!=3){
  37.                                                 N[j]=3;
  38.                                                 sum-=num[j];                                 
  39.                                             }      
  40.                                             else if(N[j-1]!=2 && N[j+1]!=2)
  41.                                                 N[j]=2;
  42.                                             else{
  43.                                                     N[j]=1;      
  44.                                                     sum+=num[j];
  45.                                                 }                                                
  46.                                         }                                       
  47.                                 }                                    
  48.                         }
  49.                         continue;
  50.             }
  51.     cout<<sum<<endl;
  52.     return 0;
  53.         }      
  54. }
複製代碼





歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2