叠放箱子解题报告

带权值的最长上升子序列
f[i]表示从后往前讨论叠放i个箱子的最小重量(因为是反向读入，其实从前往后讨论，更像最长上升子序列了）

动规方程: f[k+1]=mid(f[k+1], self[i]+f[k]) (stand[i]>=f[k]) (0<=k<i)
最长上升子序列的方程 f[i]=f[j]+1(1<=j<i, a[j]<a[i])

又一次犯了和最长上升子序列一样的算法错误
又一次屁颠屁颠地给f[1]赋了初值然后从f[2]开始讨论，
好吧，从f[2]讨论就讨论吧，可是又只从后往前讨论到f[1],真是生怕不WA.
和拦截导弹错得如出一辙，和合唱队形错得异曲同工，和射箭一样错得外焦里嫩，和矩形套矩形一样错得......
因为第一颗导弹不一定非要打出去，因为最长上升子序列不一定就得从第一个数开始。
这一堆题都是不明入口的动态规划类型，答案结构不一定包含第一个数。

 1 #include <stdio.h>
 2 #define maxn 1001
 3 #define inf 10000000
 4 int min(int a, int b)
 5 {
 6     if(a<b)    return a;
 7     return b;
 8 }
 9 int self[maxn], stand[maxn], f[maxn];
10 int main()
11 {
12     int n, i, k;
13     scanf("%d", &n);
14     for(i=n; i>=1; i--)    scanf("%d%d", &self[i], &stand[i]);            //反向读入
15     f[1]=self[1];
16     for(i=2; i<=n; i++)
17         for(f[i]=inf, k=i-1; k>=1; k--)
18             if(stand[i]>=f[k])    f[k+1]=min(f[k+1], self[i]+f[k]);    //像最长上升子序列的决策if(a[j]<a[i])    f[i]=f[j]+1(1<=j<i)
19     for(i=n; i>=1&&f[i]==inf; i--);
20     printf("%d", i);
21     return 0;
22 }

以下是错误代码，听取WA声一片

 1 #include <stdio.h>
 2 #define maxn 1001
 3 #define inf 10000000
 4 int min(int a, int b)
 5 {
 6     if(a<b)    return a;
 7     return b;
 8 }
 9 int self[maxn], stand[maxn], f[maxn];
10 int main()
11 {
12     int n, i, k;
13     scanf("%d", &n);
14     for(i=n; i>=1; i--)    scanf("%d%d", &self[i], &stand[i]);
15     for(i=1; i<=n; i++)
16         for(f[i]=inf, k=i-1; k>=0; k--)
17             if(stand[i]>=f[k])
18                 f[k+1]=min(f[k+1], self[i]+f[k]);
19     for(i=n; i>=1&&f[i]==inf; i--);
20     printf("%d", i);
21     return 0;
22 }

以下是正确代码