USACO 31 Problem 'smrtfun' Analysis

by Richard Peng

The problem asks us to optimize over two values, so we could DP on the first
value while trying to maximize the second. So our DP state is [cow to be
considered, sum of the smartness of all the cows so far] and we try to maximize
the sum of fun values of the cows.


Also, we could restrict the fun values to be positive by considering the cows
in decreasing order of funniness so once a negative fun value is reached, it's
impossible to get positive.


The transition is essentially the same as the version where 0/1s are stored in
the states, except we need to keep two arrays and rotate on them instead of
working on a single one as fun values can be negative (we also do case work
based on the sign of the fun value in order to keep things in a single array,
but that's also some added work).

Here is a sample solution:

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

struct cowtype{
	int v1,v2;
	bool operator < (const cowtype &o) const {return v1>o.v1;}
};

cowtype cow[100];
int n,lis[200000],lt,lt1,bes[2][200000],pre,cur,ans,huge;

int main(){
	int i,j,tem1;

freopen("smrtfun.in","r",stdin);
freopen("smrtfun.out","w",stdout);

	huge=-2000000000;
	cin>>n;

	for(i=0;i<n;i++)
		cin>>cow[i].v1>>cow[i].v2;

	sort(cow,cow+n);

	for(i=0;i<200000;i++)	bes[0][i]=bes[1][i]=huge;

	bes[0][0]=0;
	lis[0]=0;
	lt=1;

	for(i=0;i<n;i++){
		pre=i%2;
		cur=(i+1)%2;

		for(j=0;j<lt;j++) bes[cur][lis[j]]=bes[pre][lis[j]];

		for(lt1=lt,j=0;j<lt1;j++)
			if((tem1=lis[j]+cow[i].v1)>=0){
				if(bes[cur][tem1]==huge)
					lis[lt++]=tem1;
				bes[cur][tem1]>?=bes[pre][lis[j]]+cow[i].v2;
			}
	}

	for(ans=huge,i=0;i<lt;i++)
		if(bes[cur][lis[i]]>=0)
			ans>?=bes[cur][lis[i]]+lis[i];

	cout<