poj 3017 Cut the Sequence(DP+단일 대기열+set)

2746 단어 최적화Integerinputeachoutput
Cut the Sequence
Time Limit: 2000MS
 
Memory Limit: 131072K
Total Submissions: 7210
 
Accepted: 2025
Description
Given an integer sequence { an } of length N, you are to cut the sequence into several parts every one of which is a consecutive subsequence of the original sequence. Every part must satisfy that the sum of the integers in the part is not greater than a given integer M. You are to find a cutting that minimizes the sum of the maximum integer of each part.
Input
The first line of input contains two integer N (0 < N ≤ 100 000), M. The following line contains N integers describes the integer sequence. Every integer in the sequence is between 0 and 1 000 000 inclusively.
Output
Output one integer which is the minimum sum of the maximum integer of each part. If no such cuttings exist, output −1.
Sample Input 
8 17
2 2 2 8 1 8 2 1
Sample Output 
12
Hint
Use 64-bit integer type to hold M.
Source
POJ Monthly--2006.09.29, zhucheng
제목:http://poj.org/problem?id=3017
제목: 길이가 n인 수열을 드리겠습니다. 이 수열을 임의의 블록으로 나누십시오. 각 블록의 원소와 m보다 작으면 모든 블록의 최대치와 최소로 나누십시오.
분석: 이 문제는 곧 DP 방정식 f[i]=min {f[j]+max {a[k]}(b[i]이 방정식의 복잡도는 O(n^2)로 분명히 시간을 초과해야 한다.
그 다음에 최적화되었다. 우선 최대치의 대열을 최적화해야 한다. 이 대열의 첫 번째 원소가 현재 위치에 있는 것과 m를 초과하지 않도록 해야 한다. 이런 가능한 해답은 f[i]=f[b[i]-1]+a[q[l](즉 첫 번째 원소의 값)이다. 이것은 가장 좋은 해가 아니다. 그래서 대열의 가장 좋은 해를 찾아야 한다. 가능한 가장 좋은 해답은 이런 f[q[j]+a[q[j+1]일 뿐이다.즉, a[j]가 뒤의 수보다 크다는 것은 명백하다. 만약에 a[j]가 뒤의 수보다 작다면 우리는 a[j]를 뒤로 나누어 더 좋은 해를 얻을 수 있다. 여기에 관련된 이 가장 좋은 해를 찾는 문제를 나는 오랫동안 생각했다. O(1)의 방식을 찾고 싶었지만 ==를 찾지 못했다. 결국 포기했다. set을 사용했고 타락했다. 균형수 한 그루를 두드리지 않았다...
코드:
#include<cstdio>
#include<set>
using namespace std;
const int mm=111111;
int a[mm],q[mm];
long long f[mm],sum,tmp,m;
multiset<int> sbt;
int i,l,r,p,n;
int main()
{
    scanf("%d%I64d",&n,&m);
    sbt.clear();
    sum=l=0,f[n]=r=-1;
    for(p=i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
        while(sum>m)sum-=a[p++];
        if(p>i)break;
        while(l<=r&&a[i]>=a[q[r]])
        {
            if(l<r)sbt.erase(f[q[r-1]]+a[q[r]]);
            --r;
        }
        q[++r]=i;
        if(l<r)sbt.insert(f[q[r-1]]+a[q[r]]);
        while(q[l]<p)
        {
            if(l<r)sbt.erase(f[q[l]]+a[q[l+1]]);
            ++l;
        }
        f[i]=f[p-1]+a[q[l]];
        tmp=*sbt.begin();
        if(l<r&&f[i]>tmp)f[i]=tmp;
    }
    printf("%I64d
",f[n]);
    return 0;
}
LightOJ 1035 Intelligent Factorial Factorization
HiAI Image - Picasso와 Kotlin의 초고해상도

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage