A - Sliding Window（poj 2823）
維護兩個單調隊列，一個遞增，一個遞減，并且保持在更新答案的時候，單調隊列的長度為k
關于這題，我實在忍不住吐槽了，加上輸入輸出挂時間快了10倍以上，簡直不能忍！
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//---------------------------------------------
const int MAXN=1000010;
struct node
{
int num;
int i;
}q1[MAXN],q2[MAXN];
int maxn[MAXN],minn[MAXN];
int main()
{
int n,k,i;
while(read(n)&&read(k))
{
int top1,top2,tail1,tail2;
top1=top2=tail1=tail2=0;
int p;
for(i=0;i<n;i++)
{
read(p);
while(top1<tail1&&q1[tail1-1].num<p)
tail1--;//遞減隊列
q1[tail1].i=i,q1[tail1++].num=p;
while(top2<tail2&&q2[tail2-1].num>p)
tail2--;//遞增隊列
q2[tail2].i=i,q2[tail2++].num=p;
if(i>=k-1)
{
while(i-q1[top1].i>=k)
top1++;
while(i-q2[top2].i>=k)
top2++;
maxn[i-k+1]=q1[top1].num,minn[i-k+1]=q2[top2].num;
}
}
write(minn[0]);
for(i=1;i<=n-k;i++)
{
putchar(' ');write(minn[i]);
}
putchar('\n');
write(maxn[0]);
for(i=1;i<=n-k;i++)
{
putchar(' ');write(maxn[i]);
}
putchar('\n');
}
return 0;
}
B - Post Office （POJ1160）
a[i,j]表示在V[i..j]之間建立一個郵局的最小距離和，取中點維護
dp[i][j] = max{ dp[k][j-1] + ( min ( v[i] - v[t] , v[t] - v[k] ) , t=k+1...i-1 ) , k = j-1...i-1 }
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
//-------------------------
int v[305],a[305][305],p,n;
int dp[305][35];//代表在前x個村莊中建立y個郵局的最小的距離的
int main()
{
read(n),read(p);
for(int i=1;i<=n;i++)
read(v[i]);
for(int tmp=1;tmp<n;tmp++)
{
for(int i=0;i<=n-tmp;i++)
{
int j=i+tmp;
a[i][j]=a[i+1][j]+v[(i+1+j)/2]-v[i];
}
}
memset(dp,INF,sizeof(dp));
for(int i=1;i<=n;i++)
dp[i][1]=a[1][i];
for(int i=2;i<=p;i++)
for(int j=i;j<=n;j++)
for(int k=i;k<=j;k++)
if(dp[j][i]>dp[k][i-1]+a[k+1][j])
dp[j][i]=dp[k][i-1]+a[k+1][j];
printf("%d\n",dp[n][p]);
return 0;
}
D - Print Article（HDU 3507）
dp[i] = min{ dp[j] + ( sum[i] - sum[j] ) ^ 2 +M } 0<j<i
斜率優化：
[ ( dp[j] + sum[j] * sum[j] ) - ( dp[k] + sum[k] * sum[k] ) ] / 2 * ( sum[j] - sum[k] ) <= sum[i].
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
const int MAXN=500010;
ll c[MAXN],dp[MAXN];
ll q[MAXN];
int n,m;
ll Dp(int i,int j)
{
return dp[j]+m+(c[i]-c[j])*(c[i]-c[j]);
}
ll Up(int j,int k)
{
return fabs(dp[j]+c[j]*c[j]-(dp[k]+c[k]*c[k]));
}
ll Do(int j,int k)
{
return 2*fabs(c[j]-c[k]);
}
int main()
{
while(read(n)&&read(m))
{
for(int i=1;i<=n;i++)
{
read(c[i]);
c[i]+=c[i-1];
}
dp[0]=0;
int head=0,tail=0;
q[tail++]=0;
for(int i=1;i<=n;i++)
{
while(tail>head+1 && Up(q[head],q[head+1])<=c[i]*Do(q[head],q[head+1]))
head++;
dp[i]=Dp(i,q[head]);
while(tail>head+1 && Up(i,q[tail-1])*Do(q[tail-1],q[tail-2])<=Up(q[tail-1],q[tail-2])*Do(i,q[tail-1]))
tail--;
q[tail++]=i;
}
printf("%lld\n",dp[n]);
}
return 0;
}
G - Picnic Cows（HDU 3045）
dp[i] = dp[j] + sum[i] - sum[j] - ( i - j )* a[j+1]
斜率優化：
dp[j] - sum[j] + j * a[j+1] - ( dp[i] - sum[i] + i * a[i+1] ) / a[j+1]- a[i+1] <= i
并且維持 目标點與隊列尾 m 長度的大小
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
const int MAXN=400010;
//dp[i] = dp[j] + sum[i] - sum[j] -(i - j)*a[j+1]
ll dp[MAXN],sum[MAXN],a[MAXN];
int q[MAXN];
ll getdp(int i,int j)
{
return dp[j]+sum[i]-sum[j]-(i-j)*a[j+1];
}
ll getup(int j,int i)
{
return dp[j]-sum[j]+j*a[j+1]-(dp[i]-sum[i]+i*a[i+1]);
}
ll getdown(int j,int i)
{
return a[j+1]-a[i+1];
}
int main()
{
int t,n;
while(read(n)&&read(t))
{
for(int i=1;i<=n;i++)
read(a[i]);
sort(a+1,a+n+1);
sum[0]=0;
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
int head=0,tail=0;
dp[0]=0;
q[tail++]=0;
for(int i=t;i<=n;i++)
{
while(tail>head+1 && getup(q[head+1],q[head])<=i*getdown(q[head+1],q[head]))
head++;
dp[i]=getdp(i,q[head]);
if(i>=2*t-1)
{
int j=i-t+1;
while(tail>head+1 && getup(q[tail-1],q[tail-2])*getdown(j,q[tail-1])>=
getup(j,q[tail-1])*getdown(q[tail-1],q[tail-2]))
tail--;
q[tail++]=j;
}
}
write(dp[n]);putchar('\n');
}
return 0;
}
J - Trade
dp[i][j ]= max { dp[i-1][j] , dp[i-w-1][k] - ( j - k ) * ap[i] , dp[i-w-1][k] + ( k - j ) * bp[i] }
i 表示天數 j表示股票數
天數超過則 w 的限制則出隊
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
//-----------------
struct Node
{
int ap,bp; //price
int as,bs; //num
}a[2010];
struct Que
{
int v,i;
}q[2010];
int n,maxp,w;
int dp[2020][2020];
//dp[i][j]=max{dp[i-1][j],dp[i-w-1][k]-(j-k)*ap[i],dp[i-w-1][k]+(k-j)*bp[i]}
// i 表示天數 j表示股票數
//天數超過則推出
int main()
{
int T;
read(T);
while(T--)
{
read(n),read(maxp),read(w);
memset(dp,0xcf,sizeof(dp));
for(int i=1;i<=n;i++)
{
read(a[i].ap);read(a[i].bp);read(a[i].as);read(a[i].bs);
}
for(int i=1;i<=n;i++)
for(int j=0;j<=min(a[i].as,maxp);j++)
dp[i][j]=-a[i].ap*j;
for(int i=2;i<=n;i++)
for(int j=0;j<=maxp;j++)
dp[i][j]=max(dp[i][j],dp[i-1][j]);
for(int i=w+2;i<=n;i++)
{
int pre=i-w-1;
int head=0,tail=-1;
for(int j=0;j<=maxp;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i][j]);
Que temp;
temp.v=dp[pre][j]+j*a[i].ap;temp.i=j;
while(tail>=head&&temp.v>q[tail].v) tail--;
q[++tail]=temp;
while(tail>=head&&fabs(j-q[head].i)>a[i].as) head++;
if(tail>=head)
dp[i][j]=max(dp[i][j],q[head].v-j*a[i].ap);
}
head=0,tail=-1;
for(int j=maxp;j>=0;j--)
{
dp[i][j]=max(dp[i-1][j],dp[i][j]);
Que temp;
temp.v=dp[pre][j]+j*a[i].bp;temp.i=j;
while(tail>=head&&temp.v>q[tail].v) tail--;
q[++tail]=temp;
while(tail>=head&&fabs(j-q[head].i)>a[i].bs) head++;
if(tail>=head)
dp[i][j]=max(dp[i][j],q[head].v-j*a[i].bp);
}
}
printf("%d\n",dp[n][0]);
}
return 0;
}
![POJ 1284 Primitive Roots (歐拉函數&原根定理)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)