 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| 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 | |||||||||
请问动态规划是这样写的吗?#include <stdio.h>
#include <memory.h>
#define MAX 200001
long f[200001];
int real[200001];
int main()
{
long n,max,i,j,si,fi;
scanf("%ld",&n);
for(i=0;i<=200000;i++)f[i]=MAX;
f[100000]=0;
for(i=0;i<n;i++)
{
scanf("%ld%ld",&si,&fi);
for(j=0;j<=200000;j++)real[j]=1;
for(j=0;j<=200000;j++)
{
if(j+si>=0&&j+si<=200000)
if(f[j]!=MAX&&real[j]&&((f[j]+fi>f[j+si]&&f[j+si]!=MAX)||f[j+si]==MAX))
{
f[j+si]=f[j]+fi;
real[j+si]=0;
}
}
}
max=0;
for(i=100000;i<=200000;i++)
{
if(f[i]>=0)
if(f[i]!=MAX&&f[i]+i-100000>max)max=f[i]+i-100000;
}
printf("%ld\n",max);
}
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
