Cod sursa(job #724373)

Utilizator bacilaBacila Emilian bacila Data 26 martie 2012 14:50:15
Problema Wanted Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<fstream>
#include<algorithm>
using namespace std;
pair<int,int> a[220];
unsigned int b[220][220];
int n;
unsigned int div(int st,int dr,int tata)
{
   int i;
    if(b[st][dr]<((1<<31))&&b[st][dr])
    return b[st][dr];
if(st>dr)
return 0;
b[st][dr]=1<<31;
	for(i=st;i<=dr;i++)
	{
    	b[st][dr]=min(max(div(st,i-1,i),div(i+1,dr,i))+a[i].second+a[tata].second+max(a[tata].first-a[i].first,-a[tata].first+a[i].first),b[st][dr]); 
     }
	return b[st][dr];
}

int main()
{int  i;
ifstream f("wanted.in");
ofstream g("wanted.out");
f>>n;
for(i=1;i<=n;i++)
f>>a[i].first>>a[i].second;
sort(a+1,a+n+1);
g<<div(1,n,0);

f.close();
g.close();
}