## 12836 - Gain Battle Power

All about problems in Volume 128. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

### Re: 12836 - Gain Battle Power

I used LIS and LDS for calculating the power of a Death Eater.
Then i used a greedy technique to split the sequence.

getting WA

Is my method wrong ?

Give me some hint please ...

Code: Select all

``````#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
const double pi=acos(-1.0);
int inf=1000000007;
#define ri(N) scanf("%d",&N)
#define rll(N) cin>>N
#define Reverse(x) reverse(x.begin(),x.end())
#define all(X)  X.begin(),X.end()
#define UNIQUE(X)  X.resize(unique(all(X))-X.begin())
#define tr(container,it)  for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
//////////////////////////////////////////////////////////////////////
vector<int>v;
vector<int>comul;
int findInd(int left,int right)
{
int sum=comul[right]-comul[left-1];
int mid=sum/2;
int val=comul[left-1]+mid;
int ind=upper_bound(all(comul),val)-comul.begin();
if(ind==left)
ind++;
else
{
int sub1=abs((comul[ind-1]-comul[left-1])-(comul[right]-comul[ind-1]));
int sub2=abs((comul[ind]-comul[left-1])-(comul[right]-comul[ind]));
if(sub1>sub2)
ind++;
}
return ind;
}
ll solve(int left,int right)
{
if(left>=right)
return 0;
int ind=findInd(left,right);
ll total=comul[right]-comul[left-1];
total+=solve(left,ind-1)+solve(ind,right);
}
int main()
{
//freopen("E:/in.txt","r",stdin);
//freopen("E:/out.txt","w",stdout);
int i,j,k,l,m,n,t,kase=1;
ri(t);
while(t--)
{
ri(n);
v.clear();
for(i=0;i<n;i++)
{
ri(k);
v.push_back(k);
}
vector<int>len1,len2;
vector<int>M(n+1,inf);
M[0]=-inf;
for(i=0;i<n;i++)
{
int ind=lower_bound(all(M),v[i])-M.begin();
M[ind]=v[i];
len1.push_back(ind);
}
Reverse(v);
vector<int>M1(n+1,inf);
M1[0]=-inf;
for(i=0;i<n;i++)
{
int ind=lower_bound(all(M1),v[i])-M1.begin();
M1[ind]=v[i];
len2.push_back(ind);
}
Reverse(len2);
vector<int>power;
for(i=0;i<n;i++)
power.push_back(len1[i]+len2[i]-1);
comul.clear();
comul.push_back(0);
for(i=0;i<n;i++)
comul.push_back(power[i]+comul[i]);
printf("Case %d: %lld\n",kase++,solve(1,n));
}
return 0;
}
``````

Masum
New poster
Posts: 9
Joined: Tue Jul 10, 2012 11:39 am

### Re: 12836 - Gain Battle Power

I think this is a dp problem. Though the straight-forward dp is n^3, it requires a n^2 version to get accepted. I haven't got accepted yet, though. But greedy should be incorrect. I don't have any cases right now, may be someone else will post some.

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

### Re: 12836 - Gain Battle Power

May be you are right Masum
Let me know if you find any way (y)

Masum
New poster
Posts: 9
Joined: Tue Jul 10, 2012 11:39 am

### Re: 12836 - Gain Battle Power

Yes, now I know for sure, this is not greedy. And to optimize the dp complexity, you need Knuth optimization(may be quadrangle inequality)