| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
一直WA,试了论坛上的数据都没错了,求救中。。#include<iostream>
#include<string>
#include <algorithm>
using namespace std;
struct Gangster
{
short nTime;
int nProsperity;
int nStoutness;
bool operator<( const Gangster & g)
{
if( this->nTime < g.nTime)
return true;
else
return false;
}
};
short f[2][100+10];
int main()
{
//first to input the data
int nGangster,nTotalTime,nK;
cin>>nGangster>>nK>>nTotalTime;
Gangster * pG = new Gangster[nGangster];
for( int i = 0; i < nGangster; i++)
cin>>pG[i].nTime;
for( int i = 0; i < nGangster; i++)
cin>>pG[i].nProsperity;
for( int i = 0; i < nGangster; i++)
cin>>pG[i].nStoutness;
//to sort the gangster
sort(pG, pG + nGangster);
//now to set the default
memset( f, 0,sizeof(f));
//to deal with it
int nMax;
Gangster * p ;
for( int i = 1; i <= nTotalTime; i++)
{
for( int j = 1; j <= nK; j++)
{
f[i%2][j] = max(f[(i-1)%2][j], max(f[(i-1)%2][j-1],f[(i-1)%2][j+1]));
for( p = pG + nGangster-1; p >= pG; p--)
{
if( p->nStoutness <= nK && nTotalTime >= p->nStoutness &&p->nTime <= nTotalTime && p->nTime == i && p->nStoutness == j)
f[i%2][j] += p->nProsperity;
}
//now found it
//cout<<f[i%2][j]<<'\t';
}
//cout<<endl;
}
//find the max
nMax = f[(nTotalTime)%2][0];
for( int i = 0; i <= nK;i++)
{
//cout<<f[30000][i];
if( nMax < f[(nTotalTime)%2][i])
nMax = f[(nTotalTime)%2][i];
//cout<<f[(nTotalTime)%2][i]<<"\t";
}
cout<<nMax;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator