【DP】 TJU 4074 && CF 319C
1418 단어 dp
#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#define maxn 100005
#define eps 1e-6
#define mod 10007
#define INF 99999999
#define lowbit(x) (x&(-x))
//#define lson o<<1, L, mid
//#define rson o<<1 | 1, mid+1, R
typedef long long LL;
using namespace std;
LL a[maxn];
LL b[maxn];
LL dp[maxn];
LL q[maxn];
LL n;
void read(void)
{
int i;
for(i = 1; i <= n; i++) scanf("%lld", &a[i]);
for(i = 1; i <= n; i++) scanf("%lld", &b[i]);
}
void init(void)
{
memset(q, 0, sizeof q);
memset(dp, 0, sizeof dp);
}
double g(int aa, int bb)
{
return (dp[aa] - dp[bb]) / (b[bb] - b[aa]);
}
void work(void)
{
int h=0, t=0, i;
dp[1]=0;
q[++t] = 1;
for(i = 2; i <= n; i++) {
while(h+1 < t && g(q[h+1], q[h+2]) < a[i]) ++h;
dp[i] = dp[q[h+1]] + b[q[h+1]] * a[i];
while(h+1 < t && g(q[t-1], q[t]) >= g(q[t], i)) --t;
q[++t] = i;
}
printf("%lld
", dp[n]);
}
int main(void)
{
while(scanf("%lld", &n)!=EOF) {
read();
init();
work();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
