npsc2019_F. bb 與序列

葉桔良

F. bb 與序列
Problem ID: coloring
某天 bb 拿到了一個序列，這個序列裡面的數字有正有負也有可能有零，而 bb 想用紅、
綠、藍三種顏色幫這個序列上色。為了美觀，每個數字都必須被標上顏色，而且序列中任兩個
相鄰的數字必須要被標上不同的顏色。
由於 bb 喜歡綠色且討厭紅色，他覺得這個序列上色之後的價值是標上綠色的數字的總和
扣掉標上紅色的數字的總和。
請問在滿足上述的條件下，這個序列上色後價值可以變成多高呢？
Input
輸入的第一行有一個正整數 N，代表序列的長度。
第二行有 N 個以空格分開的整數 v1, v2, . . . vN，代表序列依序的數值。
• 1 ≤ N ≤ 106
• −1000 ≤ vi ≤ 1000
Output
輸出只有一行，代表上色之後這個序列的最高可能價值。

葉桔良

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. }

複製代碼