Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:DP

Posted by ACAccepted at 2019-02-23 20:55:46 on Problem 2576
In Reply To:DP Posted by:lzxzy at 2018-08-01 14:57:08
> //poj2576
> 
> #include <iostream>
> #include <cstdlib>
> #include <cstdio>
> #include <cmath>
> #include <cstring>
> #include <algorithm>
> using namespace std;
> int n,m,v,wei,f[105];
> int a[22505][55];
> int b[23505][55];
> 
> void into()
> {
> 	scanf("%d",&n);
> 	for(int i=1;i<=n;i++)
> 	{
> 		scanf("%d",&f[i]);
> 		wei+=f[i];
> 	}
> 	v=wei/2;m=n/2;
> 	if(n%2!=0)m++;
> }
> 
> void js()
> {
> 	for(int i=1;i<=n;i++)
> 		for(int j=v;j>=f[i];j--)
> 			for(int k=1;k<=m;k++)
> 			{
> 				if(a[j-f[i]][k-1]+1>a[j][k])
> 				{
> 					a[j][k]=a[j-f[i]][k-1]+1;
> 					b[j][k]=b[j-f[i]][k-1]+f[i];
> 				}
> 				else if((a[j-f[i]][k-1]+1==a[j][k])&&(b[j-f[i]][k-1]+f[i]>b[j][k]))b[j][k]=b[j-f[i]][k-1]+f[i];
> 			}
> 	if(wei-b[v][m]>b[v][m])printf("%d %d\n",b[v][m],wei-b[v][m]);
> 	else printf("%d %d\n",wei-b[v][m],b[v][m]);
> }
> 
> int main()
> {
> 	into();
> 	js();
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator