P1934 封印

題目描述

很久以前，魔界大旱，水井全部干涸，溫度也越來越高。為了拯救居民，夜叉族國王龍溟希望能打破神魔之井，進入人界“竊取”水靈珠，以修復大地水脈?？墒橇缰g皆有封印，神魔之井的封印由蜀山控制，并施有封印。龍溟作為魔界王族，習有穿行之術(shù)，可任意穿行至任何留有空隙的位置。然而封印不留有任何空隙！ 龍溟無奈之下只能強行破除封印。破除封印必然消耗一定的元氣。為了尋找水靈珠，龍溟必須減少體力消耗。他可以在破除封印的同時使用越行術(shù)。

神魔之井的封印共有 n 層，每層封印都有一個堅固值。身為魔族的龍溟單獨打破一層封印時需要消耗的元氣為該層封印的堅固值和封印總層數(shù) n 的平方的乘積； 但他運用越行術(shù)時，打破第 i 層到第 j 層封印(i<j)的總元氣消耗為第 i, j 層封印的堅固值之和與第 i, j 層之間所有封印層（包括第 i, j 層）的堅固值之和的乘積。同時，為了不驚動蜀山，第 i, j 層封印的堅固值之和必須不大于一個固定值 t（單獨打破時該層堅固值可以大于該值） 。

輸入輸出格式

輸入格式：

?

第一行包含兩個正整數(shù) n 和 t，按序表示封印層數(shù)和題中所述的固定值。

第二行為 n 個正整數(shù)a1~an，按序表示第 1 層到第 n 層封印的堅固值。

?

輸出格式：

?

僅一行，包含一個正整數(shù)，表示最小消耗元氣。

?

輸入輸出樣例

輸入樣例#1：?復制 6 10 8 5 7 9 3 5 輸出樣例#1：?復制 578

說明

【樣例說明】

先單獨打破第一層，再用越行術(shù)從第二層直接打破到最后一層。 這樣消耗元

氣8 × 6^2+ (5 + 5) × (5 + 7 + 9 + 3 + 5) = 578。

【數(shù)據(jù)范圍】

對于 10%的數(shù)據(jù)，n ≤ 10；

對于 50%的數(shù)據(jù)，n ≤ 100；

對于 70%的數(shù)據(jù)，n ≤ 500；

對于 100%的數(shù)據(jù)，n ≤ 1000，ai(1 ≤ i ≤ n) , t ≤ 20000。

?

?

洛谷題解：

由于題目具有無后效性，所以想到用DP來解決。

我們令f[i]表示打破前i層封印消耗元氣的最小值，則狀態(tài)轉(zhuǎn)移方程如下：

f[i]=max?{f[i?1]+a[i]*n^2,f[k]+(a[k+1]+a[i])*sum(k+1,i)|0<k+1<i,a[k+1]+a[i]≤k}

狀態(tài)轉(zhuǎn)移方程寫好后，問題在于求sum(k+1,i)時如果遍歷一遍需要O(n)的復雜度。這樣總復雜度為k(n^3)，50-70分。

這個復雜度可以用預處理前綴和的方法來優(yōu)化。用S[i]表示從a[1]到a[i]的

總和，則sum(k+1,i)=S[i]-S[k]。這樣總復雜度為k(n^2)，可以通過所有測試點。

?

?

1 #include<iostream> 2 using namespace std; 3 int n,t; 4 long long f[1003],s[1003],a[1003]; 5 int main() 6 { 7 cin>>n>>t; 8 int m=n*n; 9 for(int i=1;i<=n;i++) 10 { 11 cin>>a[i]; 12 s[i]=s[i-1]+a[i]; 13 } 14 for(int i=1;i<=n;i++) 15 { 16 long long ans=m*a[i]+f[i-1]; 17 for(int j=1;j<i;j++) 18 { 19 if(a[i]+a[j]>t)continue; 20 ans=min(ans,(a[i]+a[j])*(s[i]-s[j-1])+f[j-1]); 21 } 22 f[i]=ans; 23 } 24 cout<<f[n]; 25 return 0; 26 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Renyi-Fan/p/7773945.html

總結(jié)

以上是生活随笔為你收集整理的P1934 封印的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。