poj1821(단조 대기열 최적화 dp)
2315 단어 dp
문제풀이 사고방식: 이것은 단조로운 대열 최적화 dp의 문제이다. 우선 상태 dp[i][j]는 첫 번째 노동자가 닦은 마지막 널빤지가 j라는 것을 의미한다. 주의: 널빤지는 닦을 수 있고 닦지 않을 수 있으며 노동자도 어떤 벽도 닦지 않을 수 있다.이전에 나는 잊어버렸기 때문에 상태 방정식은 반만 맞췄다. dp[i][j]=max(dp[i][j], dp[i-1][k]+(j-k)*p[i]), 여기 또 dp[i][j]=max(dp[i][j], dp[i-1][j], dp[i][j][j], dp[i][j][j][j]])//제i는 개인이 닦지 않고 제j면 벽은 닦지 않는다.
여기서 관건은 방정식을 어떻게 최적화하는가이다. dp[i][j]=max(dp[i-1][k]-k*p[i])+j*p[i]를 주목하면 dp[i-1][k]-k*p[i]의 최대치를 직접 유지할 수 있다. 여기서 사용하는 것은 단조로운 대기열이다.
참조 블로그:http://www.cnblogs.com/proverbs/archive/2012/10/04/2711751.html
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node
{
int l,p,s;
}worker[105];
int n,k,dp[105][16005],q[16005];
int head,tail,l[105],r[105];
bool cmp(Node a,Node b)
{
return a.s < b.s;
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i = 1; i <= k; i++)
scanf("%d%d%d",&worker[i].l,&worker[i].p,&worker[i].s);
sort(worker+1,worker+1+k,cmp);
for(int i = 1; i <= k; i++)
{
l[i] = max(worker[i].s - worker[i].l,0);
r[i] = min(worker[i].s + worker[i].l - 1,n);
}
memset(dp,0,sizeof(dp));
for(int i = 1; i <= k; i++)
{
for(int j = 0; j <= n; j++) dp[i][j] = dp[i-1][j]; // i
head = tail = 0;
for(int j = l[i]; j < worker[i].s; j++) // dp[i-1]
{
int tmp = dp[i-1][j] - j * worker[i].p;
while(head < tail && dp[i-1][q[tail-1]] - q[tail-1]*worker[i].p <= tmp) tail--;
q[tail++] = j;
}
for(int j = worker[i].s; j <= r[i]; j++)
{
while(head < tail && j - q[head] > worker[i].l) head++; //
dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
dp[i][j] = max(dp[i][j],dp[i-1][q[head]] + (j - q[head]) * worker[i].p);
}
for(int j = r[i] + 1; j <= n; j++)
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
printf("%d
",dp[k][n]);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
