code forces 402B Trees in a Row

题目大意：皇家园丁奉命给英国女王造园，要造出一种奇特的景观，公园里有一行树，树高已分别给出，先要修改树高，使其满足公差为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;i
    
     sum)printf(- %d %d ,i+1,a[i]-sum); sum+=k; } return 0; }