例题3：Farmer_John收苹果

农场的夏季是收获的好季节。在Farmer John的农场，他们用一种特别的方式来收小苹果：

Bessie摇小苹果树，小苹果落下，然后Farmer John尽力接到尽可能多的小苹果。

作为一个有经验的农夫，Farmer John将这个过程坐标化。

他清楚地知道什么时候 \((1 \leq t \leq 1,000,000)\) 什么位置（用二维坐标表示，\(?1000 \leq x,y \leq 1000\)）会有小苹果落下。

他只有提前到达那个位置，才能接到那个位置掉下的小苹果。

一个单位时间，Farmer John能走 \(s (1 \leq s \leq 1000)\) 个单位。

假设他开始时 \((t=0)\) 站在 \((0,0)\) 点，他最多能接到多少个小苹果？

Farmer John 在接小苹果时，从某个点到另外一点按照直线来走。

讲苹果按照落地时间排序，可得到如下状态：

状态：\(f[i]\)：如果接第 \(i\) 个苹果，此时最多能接到的苹果个数

状态转移：\(f[i]=max(f[i],f[j]+1)\)

bool mycmp(Farmer_John a,Farmer_John b)
{
	return a.t<b.t;
}
double Sqrt(int i,int j)
{
	double k;
	k=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
	return k;
}

sort(a+1,a+1+n,mycmp);
for(int i=1;i<=n;i++)
    f[i]=-1;
f[0]=0;
for(int i=1;i<=n;i++)
{
    for(int j=0;j<i;j++)
    {
        if(f[j]>=0&&Sqrt(i,j)<=(a[i].t-a[j].t)*s)
            f[i]=max(f[i],f[j]+1);
    }
    ans=max(ans,f[i]);
}
printf("%d\n",ans);

练习1：合唱队形 Luogu P1091 [NOIP2004 提高组]

根据题意，可得如下状态：

状态：\(l[i]\)：在区间 \([1 \sim i]\) 中的最长上升子序列

? \(r[i]\)：在区间 \([n \sim i]\) 中的最长上升子序列

状态转移：当 \(j<i\) 且 \(a[i]>a[j]\) 时，\(l[i]=max(l[i],l[j]+1)\)

? 当 \(j>i\) 且 \(a[i]>a[j]\) 时，\(r[i]=max(r[i],r[j]+1)\)

for(int i=1;i<=n;i++)
    l[i]=r[i]=1;

for(int i=1;i<=n;i++)
    for(int j=1;j<i;j++)
        if(a[i]>a[j]) l[i]=max(l[i],l[j]+1);

for(int i=n;i>=1;i--) 
    for(int j=n;j>i;j--)
        if(a[i]>a[j]) r[i]=max(r[i],r[j]+1);

for(int i=1;i<=n;i++)
    minn=min(minn,n-l[i]-r[i]+1);
printf("%d\n",minn);

练习2：轮船问题

某国家被一条河划分为南北两部分，在南岸和北岸总共有 \(N\) 对城市

每一城市在对岸都有一个城市作为友好城市。

每一对友好城市都希望有一条航线来往，于是他们向政府提出了申请。

政府决定允许开通的航线就互不交叉（如果两条航线交叉，将有很大机会撞船）。

兴建哪些航线以使在安全条件下有最多航线可以被开通。

根据题意，将航线按照北岸的距离从小到大排序

此时南岸的距离所组成的序列中，找出最长上升子序列即可

sort(a+1,a+1+n,mycmp);
for(int i=1;i<=n+1;i++)
    dp[i]=INF;
dp[1]=a[1].d;
for(int i=2;i<=n;i++)
    *lower_bound(dp+1,dp+1+n,a[i].d)=a[i].d;
int ans=lower_bound(dp+1,dp+1+n,INF)-(dp+1);
printf("%d\n",ans);

练习3：护卫队 Luogu P1594

状态：\(f[i]\)：前 \(i\) 辆车通过所需的最小时间

由于数组 \(f\) 为 double 类型，min函数只能进行整形之间的比较大小

我们需要自己写一个 Min 函数进行两个 double 类型比较大小

double Min(double a,double b)
{
	if(a>b) return b;
	else return a;
}

状态转移：\(f[i]=min(f[i],f[j-1]+l/V)\)

初值：\(f[1]=l/s[1]\) （只有一辆车时花的时间肯定是桥的长度/这辆车的速度）

l*=60;//把每个s都除以60进行时间计算，不如直接将l乘以60
for(int i=1;i<=n;i++)
    f[i]=INF;
f[1]=l/s[1];
for(int i=2;i<=n;i++)
{
    double V=s[i];
    long long W=0;//W代表重量，即当前这一组的所有车的重量之和
    for(int j=i;j>=1;j--)
    {
        if(W+w[j]>v) break;
        W+=w[j];
        V=Min(V,s[j]);//每一组的速度取所有车中速度最小的一辆车的速度 
        f[i]=Min(f[i],f[j-1]+l/V);
    }
}
printf("%.1lf\n",f[n]);

（二）动态规划的要素和动机

例题1：音量调节 Luogu P1877 [HAOI2012]

状态：\(f[i][j]\)：第 \(i\) 次修改之后，能否将音量改为 \(j\)

状态转移：\(f[i][j]=f[i][j]|f[i-1][j \pm a[i]]\)

f[0][beginlevel]=1;
for(int i=1;i<=n;i++)
{
    for(int j=maxlevel;j>=0;j--)
    {
        if(j-a[i]>=0) f[i][j]|=f[i-1][j-a[i]];
        if(j+a[i]<=maxlevel) f[i][j]|=f[i-1][j+a[i]];
    }
}
for(int i=maxlevel;i>=0;i--)
{
    if(f[n][i]) 
    {
        printf("%d\n",i);
        return 0;
    }
}
printf("-1\n");