【转】http://blog.csdn.net/zxy_snow/article/details/6002534
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <memory.h>
#include <limits.h>
#include <stack>
#define N 1010
using namespace std;
typedef struct
{
int w,s,num;
}MICE;
MICE mice[N];
stack<int> S;
int cmp(const void *a,const void *b)
{
MICE *x = (MICE*)a;
MICE *y = (MICE*)b;
if( x->w == y->w )
return -y->s + x->s;
else
return x->w - y->w;
}
int ind[N];
int main(void)
{
int n=0,len[N];
while( cin >> mice[n].w >> mice[n].s )
{
mice[n].num = n;
n++;
}
memset(ind,0,sizeof(ind));
memset(len,0,sizeof(len));
qsort(mice,n,sizeof(MICE),cmp);
len[0] = 1;
for(int i=1; i<n; i++)
{
int sum = 0,temp;
for(int j=0; j<i; j++)
if( len[j] > sum && mice[i].w > mice[j].w && mice[i].s < mice[j].s )
{
temp = j;
sum = len[j];
}
if( sum != 0 )
ind[i] = temp;
else
ind[i] = 0;
sum++;
len[i] = sum;
}
int max = 0,tempi;
for(int i=0; i<n; i++)
if( len[i] > max )
max = len[tempi=i];
cout << max << endl;
int i = tempi;
while( ind[i] != 0 )
{
S.push(mice[i].num+1);
i = ind[i];
}
S.push(mice[i].num+1);
while( !S.empty() )
{
cout << S.top() << endl;
S.pop();
}
return 0;
}
分享到:
相关推荐
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码
DP:1011 NTA 简单题1013 Great Equipment 简单题1024 Calendar Game 简单题1027 Human Gene Functions 简单题1037 Gridland 简单题1052 Algernon's Noxious Emissions 简单题1409 Communication System 简单题,但是...
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
zoj1027解题指南和代码,还不错,是学校培训给的。
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
zoj吐血制作,希望大家喜欢
能AC 通过的c++代码,包括zoj1002,1091,1789