Seemingly easy DP problem
Posted: Sun Aug 21, 2005 6:23 pm
Given a sequence of integers and an integer P find the length longest streak S such that sum of numbers in S is <= P.
Code: Select all
#include<stdio.h>
#include<stdlib.h>
const int maxN=1000000;
int a[maxN+1];
int check(int *a,int n,int p,int len)
{
int i,j,k;
for(i=1;i<n;i++) a[i]+=a[i-1];
for(i=n;i>0;i--) a[i]=a[i-1];
a[0]=0;
int le=0;
for(i=0;i<n;i++)
for(j=i;j<n;j++)
if(a[j+1]-a[i]<=p) {
if(j+1-i>le) le=j+1-i;
}
return len==le;
}
void data(int *a,int &n,int &p)
{
int i,j,k;
n=rand()%1000+1;
p=rand()%1000;
for(i=0;i<n;i++) a[i]=rand()%1000;
}
int main()
{
int i,j,n,p;
for(int run=0;run<1000;run++) {
data(a,n,p);
// scanf("%d",&p); for(i=0;i<n;i++) scanf("%d",&a[i]);
int len=0,sum=0;
int s=0,t=0;
i=-1,j=0;
while(i<n) { // invariant: sum(a[j]-a[i])<=p
while(++i<n){
sum+=a[i];
if(sum>p) break;
}
if(i-j>len) s=j+1, t=i, len=i-j;
while(sum>p) sum-=a[j++]; // keep the invariant
}
/*
printf("n %d p %d\n",n,p);
for(i=0;i<n;i++) printf("%4d",a[i]);
printf("\n%d=>%d len: %d\n",s,t,len);
*/
if(!check(a,n,p,len)) printf("\nErr");
}
}Code: Select all
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
struct prefix
{
int sum,pos;
prefix(int sum,int pos): sum(sum), pos(pos) {}
bool operator< (const prefix &pr) const
{
return (sum < pr.sum);
}
};
int solve(vector<int> seq, int p)
{
int n = seq.size();
/* Find all prefix sums of given sequence and store them in vector ps. */
vector<prefix> ps;
ps.push_back(prefix(0, -1));
int s = 0;
for (int i = 0; i < n; ++i)
{
s += seq[i];
ps.push_back(prefix(s, i));
}
/* Sort prefixes in nondecreasing order of sum. */
sort(ps.begin(), ps.end());
/* For every i: mp[i] = min(ps[i].pos, ps[i+1].pos, ...) */
vector<int> mp(ps.size());
int k = ps.back().pos;
for (int i = ps.size() - 1; i >= 0; --i)
{
k = min(k, ps[i].pos);
mp[i] = k;
}
/* Find longest streak with sum <= p. */
int res = 0;
int j = 0;
for (int i = 0; i < ps.size(); ++i)
{
while (j < ps.size() && ps[i].sum - ps[j].sum > p) ++j;
if (j >= ps.size()) break;
res = max(res, ps[i].pos - mp[j]);
}
return res;
}