题解 - Vijos

1

z20c12h LV 9 @ 2017-07-12 10:51:38

推进！


#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

struct A_DATA_TREE {
    
    int id;
    int cnt,val,cost;   

};

bool A_DATA_CMP (A_DATA_TREE tp1,A_DATA_TREE tp2) { 

    return tp1.cnt<tp2.cnt;     
    
}

A_DATA_TREE Adt[110]; 

int n,m;
int Cross[110][110];
int Ans=0;

int Dp[110][1010];

int main () {
    
    ios::sync_with_stdio(false);
    
    cin>>n>>m;
    
    for(int i=1;i<=n;i++) {
        
        Adt[i].id=i;
        cin>>Adt[i].cnt>>Adt[i].val>>Adt[i].cost;   
        
    }
    
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        cin>>Cross[i][j];

    sort(Adt+1,Adt+n+1,A_DATA_CMP);
    
    memset(Dp,0,sizeof(Dp));
    
    for(int i=1;i<=n;i++) 
      for(int j=0;j<i;j++) {
        
          if (Adt[i].cnt==Adt[j].cnt) continue;
        
          int tval=Adt[i].val,tcost=Adt[i].cost+Cross[Adt[j].id][Adt[i].id];
        
          for(int o=m-tcost;o>=0;o--) {
            
              Dp[i][o]=max(Dp[i][o],Dp[j][o+tcost]+tval); 
              Ans=max(Ans,Dp[i][o]);
            
          }        
             
    }
    
    cout<<Ans<<endl;
    
  return 0; 
    
}

0

HeRaNO (heran1999) LV 10 @ 2015-12-08 19:39:05

//简单易懂的代码 By 28814O
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct fruit
{
long num;
long value;
long time;
long before;
};

long limitime, tree;
fruit a[101];
long treetime[101][101]={ 0 }, f[110][1010] = { 0 };
long i, j, k, maxl = 0;

long max(long x, long y)
{
return x > y ? x : y;
}

int main()
{
//freopen("fruit.in","r",stdin);
//freopen("fruit.out","w",stdout);
cin >> tree >> limitime;
for (i = 1; i <= tree; i++)
{
scanf("%ld%ld%ld", &a[i].num, &a[i].value, &a[i].time);
a[i].before = i;
}
for (i = 1; i <= tree; i++)
for (j = 1; j <= tree; j++)
scanf("%ld", &treetime[i][j]);

for (i = 1; i <= tree - 1; i++)
for (j = 1; j <= tree - i; j++)
{
if (a[j].num > a[j + 1].num)
swap(a[j], a[j + 1]);
}

for (i = 1; i <= tree; i++)
for (j = limitime; j >= 0 ; j--)
for (k = i-1; k >= 0; k--)
{
if (j - treetime[a[k].before][a[i].before] - a[i].time>=0 && a[i].num > a[k].num)
{
f[i][j] = max(f[i][j], f[k][j - treetime[a[k].before][a[i].before] - a[i].time] + a[i].value);
maxl = max(maxl, f[i][j]);
}
}
cout << maxl;
return 0;
}

0

神犇 LV 10 @ 2012-09-10 00:54:09

一星半纪念

0

明慧 LV 10 @ 2009-11-10 17:23:38

求秒杀方法

0

naneux LV 8 @ 2009-11-10 16:03:27

编译通过...

├ 测试数据 01：答案正确... 25ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25m

0

赫敏·格兰杰 LV 10 @ 2009-11-09 20:56:46

-我怎么快排都写不对......

0

qwe098lth LV 8 @ 2009-11-08 20:56:41

竟然是要写sizeof(long)*4;

一个下午啊...

编译通过...

├ 测试数据 01：答案正确... 56ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：56ms

#include

#include

#define max(x,y) ((x)>(y)? (x):(y));

long n,m;

long a[101][4]={0};

long t[101][101]={0};

long f[101][1001]={0};

long ans=0;

int cmp(const void *x,const void *y)

{

return ((long *)x)[0]-((long *)y)[0];

}

int main()

{

scanf("%ld%ld",&n,&m);

long i,j,k;

for(i=1;i

0

darin LV 10 @ 2009-11-06 21:07:48

......看题的时候想着一定一定要注意是严格递增的,,可是老是编着编着就忘了,,结果wa了一次..哎..写程序一定要严格严谨啊....

0

huyuanming11 LV 10 @ 2009-10-06 21:11:06

编译通过...

├ 测试数据 01：答案正确... 619ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 259ms

├ 测试数据 09：答案正确... 353ms

├ 测试数据 10：答案正确... 478ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1709ms

没排序啊

0

我是天才他哥 LV 10 @ 2009-10-06 12:40:28

AC AC

弱智题

排序后背包

0

dfx3393521 LV 10 @ 2009-09-17 11:51:08

编译通过...

├ 测试数据 01：答案正确... 9ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

0

yzl609271536 LV 10 @ 2009-09-05 18:35:47

编译通过...

├ 测试数据 01：答案正确... 9ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

0

zhengfangyi LV 10 @ 2009-08-07 21:55:54

我来了..

0

zhanghanyuan LV 10 @ 2009-08-05 10:31:37

编译通过...

├ 测试数据 01：答案正确... 72ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：97ms

小爽一把

0

340508965 LV 10 @ 2009-07-27 15:30:04

编译通过...

├ 测试数据 01：答案正确... 9ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：18ms

很伤心不是秒杀

所以晒晒程序

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--

program p4;

var n,time,i,j,ans,m:longint;

a,s,c,x:array[0..102] of longint;

t,f:array[0..102,0..1002] of longint;

procedure qsor(head,tail:longint);

var q,e,temp,co:longint;

begin

q:=head; e:=tail; co:=a[(q+e)div 2];

repeat

while a[q]co do dec(e);

if q=e;

if head

0

474182029 LV 8 @ 2009-06-24 15:47:39

好难。。。。数组开的太小却被提醒为错误答案。。

0

唐钰小宝 LV 10 @ 2009-04-06 01:08:54

Accepted 有效得分：100 有效耗时：0ms

O(n^2m)

在排序的时候一定要纪录原来的序号啊！在用距离的时候用的是原来的序号，这样才对！

不然距离的连接矩阵会错乱！！

0

18317an7 LV 10 @ 2009-04-02 23:38:16

排序了还要确定个数是否比前一堆大，因为要求是严格递增的~~WA了3次是在第一个点上~~

编译通过...

├ 测试数据 01：答案正确... 181ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 40ms

├ 测试数据 09：答案正确... 87ms

├ 测试数据 10：答案正确... 118ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：426ms

0

Beta LV 6 @ 2009-04-03 23:37:02

编译通过...

├ 测试数据 01：答案正确... 56ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：90ms

谢谢主教对我的提醒，其实真的不用排序，用排序写的程序很长啊

不明白可以参考下面5颗星的同志

0

oimaster LV 10 @ 2009-01-27 16:20:45

注意排序后距离也要变啊！

题解

56 条题解

采果子

信息

状态

开发

支持

题解

56 条题解

采果子

信息

状态

开发

支持

还没有账户？

登录