题目链接:http://poj.org/problem?id=1180
题目大意:见黑书153页,哎,因为一个细节wrong了很久,我太水了
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 11000
//#define __int64 long long
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
__int64 dp[Max];
int n,m;
__int64 s;
int q[Max];
__int64 f[Max],t[Max],F[Max],T[Max];
int main()
{
int i,j;
//while(!=EOF)
//{
scanf("%d%I64d",&n,&s);
for(i=1;i<=n;i++)
{
scanf("%I64d%I64d",&T[i],&F[i]);
}
t[n+1]=0;f[n+1]=0;
for(i=n;i>=1;i--)
{
t[i]=t[i+1]+T[i];
f[i]=f[i+1]+F[i];
}
int top=0,tail=0;
//dp[n]=(s+t[n]-t[n+1])*f[n];
q[tail]=n+1;//开始没有把这个决策加进去,wrong了很久,血的教训啊!!!!
tail++;
for(i=n;i>=1;i--)
{
while(tail-top>= 2&&dp[q[top+1]]-dp[q[top]]<=(t[q[top+1]]-t[q[top]])*f[i])
{
top++;
}
dp[i]=dp[q[top]]+(s+t[i]-t[q[top]])*f[i];
while(tail-top>=2&&(dp[i]-dp[q[tail-2]])*(t[q[tail-1]]-t[q[tail-2]])<(dp[q[tail-1]]-dp[q[tail-2]])*(t[i]-t[q[tail-2]]))
{
tail--;
}
q[tail]=i;
tail++;
}
printf("%I64d\n",dp[1]);
// }
}
分享到:
相关推荐
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告