|
|
|
|
描述 Description |
|
|
|
Lyl今天心情不错，于是走到埃及郊外旅游(会不会碰到MMY?...PS:MMY的含义请自行理解)。他边走边向四周望望，发现周围有许多果树。这些树之间互相到达的时间Lyl是知道的（假定每两棵树之间都拥有独立的边可以到达）。他数出了这些果树上果子的个数，并且估了估每个的价格（真是个奇怪的人）。Lyl规定了一种采摘方案，就是对于第i棵树来说，它有a[i]个果子，且所有果子价值为s[i]，摘取时间为c[i](小时)。并且，当他摘了第i个树上的果子后，后面他所选择去摘的果树上的果子数必须大于第i棵树上的果子数目，说白了就是一个上升序列；并且每到一棵树，他都必须摘下该树上的所有果子。一开始，Lyl可以在任意一棵树，他只有m小时，那么，在他所拥有的限定时间内，他想知道，这样摘取的最大价值是多少？ |
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
第一行2个数：n（表示这条路上的大树数），m（总共时间）
接下来第n+1行，每行三个数a[i],s[i],c[i] (第i+1行输入的为第i颗果树的信息)
且保证有1<=a[i]<=2^31-1;1<=s[1]+s[2]+…+s[n]<=2^31-1;s[i]>=0; 1<=c[i]<=100
接下来的n行，每行n个数，第i行第j个数表示从树i到树j的时间。（0<=T[I,j]<=100;）
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
仅有一个数，即按这样方法摘取的最大价值. |
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
各个测试点1s
|
|
|
|
|
|
|
|
注释 Hint |
|
|
|
对于60%的数据 ,1<=N<=60,1<=m<=100;
对于100%的数据 ,1<=N<=100, 1<=m<=1000.
|
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1370 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
