程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> code forces 402B Trees in a Row

code forces 402B Trees in a Row

編輯:C++入門知識

 

題目大意:皇家園丁奉命給英國女王造園,要造出一種奇特的景觀,公園裡有一行樹,樹高已分別給出,先要修改樹高,使其滿足公差為k的等差數列(遞增)。一次操作課將一棵樹修改成任意高度(雖然這顯然不科學),問最少的操作數。

題目分析:要使操作數最小,就要找到最長的等差序列(可以不連續),然後一這一序列為標准,修改其余樹。具體操作方法……還是說一說吧。除了定義一個數組存樹高外,還要再定義一個,存從第一棵樹到當前樹有幾個符合以當前樹為標准的等差數列(由於樹高不可小於等於0,可剪枝),此數組初始化為1(最少就是當前元素自己)。輸入一個數後向前找如果找到大於1的,就+1存下,判斷是否大於最大值並記錄。

code:

 

#include
int main()
{
    int i,j,n,k,a[1010],b[1010],sum=1,pos=0;
    scanf(%d%d,&n,&k);
    for(i=0;i=j;j++)
        {//從後往前捋,看有沒有等差對位的
            if(a[i-j]==a[i]-j*k)
            {
                if(b[i-j]>1)b[i]=b[i-j]+1>b[i]?b[i-j]+1:b[i];//b[i]=max(b[i],b[i-j]+1);
                else b[i]=2>b[i]?2:b[i];
            }
            if(b[i]>sum)
            {
                //printf(sum==%d   :   b[%d]==%d
,sum,i,b[i]);
                sum=b[i],pos=i;//記錄
                break;//找到了就沒必要再往下找了,因為下面即使有也肯定已經找到過了
            }
        }
    }
    printf(%d
,n-sum);
    sum=a[pos]-pos*k;
    for(i=0;isum)printf(- %d %d
,i+1,a[i]-sum);
        sum+=k;
    }
    return 0;
}
PS:好慘啊……改了很長時間

 

 

 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved