題目大意:皇家園丁奉命給英國女王造園,要造出一種奇特的景觀,公園裡有一行樹,樹高已分別給出,先要修改樹高,使其滿足公差為k的等差數列(遞增)。一次操作課將一棵樹修改成任意高度(雖然這顯然不科學),問最少的操作數。
題目分析:要使操作數最小,就要找到最長的等差序列(可以不連續),然後一這一序列為標准,修改其余樹。具體操作方法……還是說一說吧。除了定義一個數組存樹高外,還要再定義一個,存從第一棵樹到當前樹有幾個符合以當前樹為標准的等差數列(由於樹高不可小於等於0,可剪枝),此數組初始化為1(最少就是當前元素自己)。輸入一個數後向前找如果找到大於1的,就+1存下,判斷是否大於最大值並記錄。
code:
#includePS:好慘啊……改了很長時間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;i sum)printf(- %d %d ,i+1,a[i]-sum); sum+=k; } return 0; }