求解两道算法中使用动态规划来做的题。

第一题 N平方级 *最好理解 使用于绝大部分此类问题
int a[N],len[N],last[N];
len[1]=1;len[2~N]=0;last[1]=0;
for(i=2~n)
for(j=1~i-1)
if(a[j]<=a[i]&&len[j]+1 len[i]=len[j+1]
last[i]=j;
}
len[i]表示到i为止 最长子串长度

第一题 N级（不能保存串 但可以输出串长）
int a[N],len[N],table[N]
table[0]=-MAX;
for(i=1~n){
j=0;
while(table[j]<=a[i]) j++;
table[j+1]=a[i];
len[i]=j+1;
}
len[i]表示到i为止 最长子串长度

第二题 dp[i][j]表示把第i到第j根钢管合并最小花费
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j||j==k||i==k) continue;
dp[i][j]=min(dp[i][j],
dp[i][k]+dp[k][j]+sum(i,k)+sum(k,j))