（复习次数：1）HDU 1160 FatMouse‘s Speed【C++练习题】

http://acm.hdu.edu.cn/showproblem.php?pid=1160

写代码还是有那么绕有那么困难的
把数组从1计数会好很多
动态规划
找LIS一样的：要么接，要么新开
之后要记录序号啊，路径啊，用数组序号记录就好
开心啊，一遍AC，我感觉又多了些自信
因为判断了边界条件：什么也没有
要特判一下，不能输出两个0了

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define N 1005
using namespace std;
struct Mouse{
    int w,s,num,last,sum;//重量，速度，代号，上一个找到的老鼠,总共多少个 
}m[N];//存老鼠 
bool mycmp(Mouse a,Mouse b){
    return a.w<b.w;
}
void print(int now){
    if(m[now].last){
    print(m[now].last);}if(now)printf("%d\n",m[now].num);//特判0
}
int main()
{
    //FILE*fp=fopen("text.in","r");//------记得最后注释掉！！ mem(m,0);//输入int cnt=0;int tw,ts;while(~scanf("%d%d",&tw,&ts)){
    //while(~fscanf(fp,"%d%d",&tw,&ts)){
    cnt++;m[cnt].num=cnt;m[cnt].w=tw;m[cnt].s=ts;}//排重量,递增（同重量最好速度最快，或者速度递增方便） sort(m+1,m+cnt+1,mycmp);//找最长递减速度//m[i].sum=max(m[j（i前，i.s小于j.s）].sum)+1; m[i].last=j; m[1].sum=1;for(int i=2;i<=cnt;i++){
    //找m[mj] int mj=0;for(int j=1;j<i;j++){
    if(m[i].s<m[j].s){
    if(m[mj].sum<m[j].sum){
    mj=j;}}}//接上（接0表新开） m[i].sum=m[mj].sum+1;m[i].last=mj;}//找到max的cnt输出，输出序号，递归 m[j].numint mi=0;for(int i=1;i<=cnt;i++){
    if(m[mi].sum<m[i].sum){
    mi=i;}}printf("%d\n",m[mi].sum);print(mi); return 0;
}

复习代码：
5/17
几个月以来，进步了许多，
能独立想出动态规划了，以已有多少为状态，
优化了，不用重复看相同个数的较大者。
还有重载、STL栈的使用
注意输出顺序

#include<bits/stdc++.h>
#ifdef LOCAL
FILE*FP=freopen("text.in","r",stdin);
//FILE*fp=freopen("text.out","w",stdout);
#endif
using namespace std;
#define N 1005
struct Mouse{
    int m,v,k,p=-1;//质量，速度，编号，父节点 
}a[N];
istream& operator>>(istream& input,Mouse &a){
    input>>a.m>>a.v;return input;
}
bool mycmp(Mouse a,Mouse b){
    if(a.m!=b.m)return a.m<b.m;return a.v<b.v;
}
int f[N],v[N],num=0;//lca第i个的值和编号 ,有第几个了 
int main(){
    int cnt=0;while(cin>>a[++cnt])a[cnt].k=cnt;cnt--;sort(a+1,a+cnt+1,mycmp);f[0]=0x3f3f3f3f;//memset(f,0x3f,sizeof(int)*(cnt+1));for(int i=1;i<=cnt;i++){
    for(int j=num;j>=0;j--){
    if(f[j]>a[i].v&&f[j+1]<a[i].v){
    //易错，举例 f[j+1]=a[i].v;v[j+1]=i;a[i].p=v[j];if(j==num)num++;break;}}}printf("%d\n",num);stack<int>ans; for(int s=v[num];s;s=a[s].p){
    ans.push(a[s].k);//printf("%d\n",a[s].k);//printf(" %d %d %d\n",a[s].m,a[s].v,a[s].p);}while(!ans.empty()){
    printf("%d\n",ans.top());ans.pop();}
}