hdu1160

￡神魔★判官ぃ 2021-10-19 11:12 240阅读 0赞

[http://acm.hdu.edu.cn/showproblem.php?pid=1160][http_acm.hdu.edu.cn_showproblem.php_pid_1160]

dp问题：

状态转移——>:

a\[i\]=a\[j\]+1;  
b\[i\]=j; //记录找到最下降序列的路径, 即下标标号

思路：先按照重量递增排序，如果w相等，则按照速度v的递减顺序排序，最后找出以速度为关键字的递减最大子序列即可。

代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

\#include < iostream >   
\#include < algorithm >   
 using  namespace  std;  
  
 int  b\[ 1001 \];  
 int  a\[ 1001 \];  
 int  c\[ 1001 \];  
  
 struct  node  
\{  
 int  w;  
 int  v;  
 int  sign;  
  
\}s\[ 1001 \];  
 int  cmp(node x, node y)  
\{  
 if (x.w == y.w)  return  x.v > y.v;  
 return  x.w < y.w;  
\}  
 int  main()  
\{  
 int  i,j,flag =- 1 ,k = 1 ;  
  
 while (scanf( " %d %d " , & s\[k\].w,  & s\[k\].v) != EOF)  
\{  
s\[k\].sign = k;  
k \++ ;  
\}  
sort(s,s \+ k,cmp);  
 int  Max = 0 ;  
 int  p;  
  
 for (i = 1 ;i < k;i \++ )  
\{  
a\[i\] = 1 ; b\[i\] =- 1 ;  
 for (j = i \- 1 ;j >= 1 ;j \-- )  
\{  
 if (s\[i\].w > s\[j\].w  &&  s\[i\].v < s\[j\].v  &&  a\[j\] \+ 1 > a\[i\])  
\{  
a\[i\] = a\[j\] \+ 1 ;  
b\[i\] = j; //记录找到最下降序列的路径, 即下标标号   
\}  
\}  
  
 if (a\[i\] > Max)  
\{  
Max = a\[i\];  
flag = i;  
\}  
\}  
  
cout << Max << endl;  
 int  t = 0 ;  
 while (flag !=- 1 )  
\{  
c\[t\] = flag;  
flag = b\[flag\];  
t \++ ;  
\}  
 for (i = t \- 1 ;i >= 0 ;i \-- )  
cout << s\[c\[i\]\].sign << endl;  
  
 return  0 ;  
\}

转载于:https://www.cnblogs.com/FCWORLD/archive/2011/05/03/2035457.html

[http_acm.hdu.edu.cn_showproblem.php_pid_1160]: http://acm.hdu.edu.cn/showproblem.php?pid=1160
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211018/495253451d434df3b39428633fbbcd33.png