国产亚洲精品福利在线无卡一,国产精久久一区二区三区,亚洲精品无码国模,精品久久久久久无码专区不卡

當(dāng)前位置: 首頁(yè) > news >正文

湖北華亞建設(shè)工程有限公司網(wǎng)站超級(jí)優(yōu)化

湖北華亞建設(shè)工程有限公司網(wǎng)站,超級(jí)優(yōu)化,如何申請(qǐng)域名做網(wǎng)站知乎,閬中網(wǎng)站建設(shè)01hl題目鏈接 好久沒有寫題了復(fù)健一下qwq 題目大意 解題思路 這題目還挺妙的 首先考慮比較正常的dp, d p [ i ] [ j ] dp[i][j] dp[i][j] 為前 i i i的長(zhǎng)度選 j j j個(gè)長(zhǎng)度的最大價(jià)值,那么轉(zhuǎn)移方程是: 圖片來(lái)自:圖片來(lái)源 但是這個(gè)是 …

題目鏈接
好久沒有寫題了復(fù)健一下qwq


題目大意

在這里插入圖片描述


解題思路

這題目還挺妙的
首先考慮比較正常的dp, d p [ i ] [ j ] dp[i][j] dp[i][j] 為前 i i i的長(zhǎng)度選 j j j個(gè)長(zhǎng)度的最大價(jià)值,那么轉(zhuǎn)移方程是:
圖片來(lái)自:圖片來(lái)源
圖片來(lái)自https://www.cnblogs.com/ACMER-XiCen/p/17660694.html
但是這個(gè)是 O ( n k 2 ) O(nk^2) O(nk2)無(wú)法通過(guò)把絕對(duì)值展開進(jìn)行討論
在這里插入圖片描述

  • 我們可以看到 d p [ i ] [ j ] dp[i][j] dp[i][j]其實(shí)都是由對(duì)角線上的 d p dp dp + + +幾個(gè) a a a, b b b的計(jì)算,那么我們可以把前面的部分用新的數(shù)組維護(hù)起來(lái)因?yàn)槎际菍?duì)角上的數(shù)值那么 i ? j i-j i?j是固定值那么就是 f [ 0 / 1 / 2 / 3 ] [ i ? j ] f[0/1/2/3][i-j] f[0/1/2/3][i?j]里面取最大值 + + +后綴部分
  • 然后因?yàn)檫@個(gè)雖然是對(duì)角線的上值的前 k k k里面的最大值,但是其實(shí) d p [ i ] [ j ] > d p [ i ? 1 ] [ j ? 1 ] dp[i][j]>dp[i-1][j-1] dp[i][j]>dp[i?1][j?1]是一定成立的所以 f [ 0 / 1 / 2 / 3 ] [ i ? j ] f[0/1/2/3][i-j] f[0/1/2/3][i?j]只用從 k = 1 k=1 k=1轉(zhuǎn)移就行
				f[0][i - j] = std::max(f[0][i - j], dp[i - 1][j - 1] - a[i] - b[i]);f[1][i - j] = std::max(f[1][i - j], dp[i - 1][j - 1] + a[i] - b[i]);f[2][i - j] = std::max(f[2][i - j], dp[i - 1][j - 1] - a[i] + b[i]);f[3][i - j] = std::max(f[3][i - j], dp[i - 1][j - 1] + a[i] + b[i]);
  • 記住f數(shù)組要初始化為負(fù)無(wú)窮,不能是0
memset(f,0x80,sizeof(f));
  • 整體代碼
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 3005;
typedef long long ll;
const ll mod = 998244353;
int a[maxn], b[maxn];
ll dp[maxn][maxn], f[4][maxn]; 
int main() {//freopen("1.txt","r",stdin);int T;scanf("%d",&T);while(T --) {int n, k;scanf("%d%d",&n,&k);memset(f,0x80,sizeof(f));// 這個(gè)0x80初始化出來(lái)是復(fù)數(shù) for(int i = 1; i <= n; ++ i) cin >> a[i];for(int i = 1; i <= n; ++ i) cin >> b[i]; for(int i = 1; i <= n; ++ i) {for(int j = 1; j <= k && j <= i; ++ j) {dp[i][j] = dp[i-1][j];f[0][i - j] = std::max(f[0][i - j], dp[i - 1][j - 1] - a[i] - b[i]);f[1][i - j] = std::max(f[1][i - j], dp[i - 1][j - 1] + a[i] - b[i]);f[2][i - j] = std::max(f[2][i - j], dp[i - 1][j - 1] - a[i] + b[i]);f[3][i - j] = std::max(f[3][i - j], dp[i - 1][j - 1] + a[i] + b[i]);dp[i][j] = std::max(dp[i][j], f[0][i - j] + a[i] + b[i]);dp[i][j] = std::max(dp[i][j], f[1][i - j] + a[i] - b[i]);dp[i][j] = std::max(dp[i][j], f[2][i - j] - a[i] + b[i]);dp[i][j] = std::max(dp[i][j], f[3][i - j] - a[i] - b[i]);
//                for(int h = 1; h <= j; ++ h) {
//                    dp[i][j] = max(dp[i-h][j-h]+abs(a[i]-b[i-h+1])+abs(a[i-h+1]-b[i]),dp[i][j]);
//                    // printf("%d %d %lld\n",i,j,dp[i][j]);
//                }}}printf("%lld\n",dp[n][k]);} return 0;
}
  • 上面你可能會(huì)疑問這個(gè)不是抵消了嗎?
f[0][i - j] = std::max(f[0][i - j], dp[i - 1][j - 1] - a[i] - b[i]);
dp[i][j] = std::max(dp[i][j], f[0][i - j] + a[i] + b[i]);

注意其實(shí)這里的有個(gè)影響是 f [ 0 ] [ i ? j ] f[0][i - j] f[0][i?j]是包含了帶 k k k的參數(shù) 所以要做兩次 m a x max max, d p [ i ? 1 ] [ j ? 1 ] ? a [ i ] ? b [ i ] dp[i - 1][j - 1] - a[i] - b[i] dp[i?1][j?1]?a[i]?b[i]只是剛好這一層兒而已

http://aloenet.com.cn/news/44266.html

相關(guān)文章:

  • 蘇州市相城區(qū)住房和城鄉(xiāng)建設(shè)局網(wǎng)站網(wǎng)絡(luò)媒體推廣方案
  • 鄭州網(wǎng)站制作怎么樣江蘇seo平臺(tái)
  • app界面模板免費(fèi)下載百度網(wǎng)站排名優(yōu)化
  • 網(wǎng)上發(fā)布信息的網(wǎng)站怎么做的百度廣告競(jìng)價(jià)
  • 提供佛山順德網(wǎng)站建設(shè)網(wǎng)站seo優(yōu)化軟件
  • 專業(yè)廣州網(wǎng)站建設(shè)臨沂網(wǎng)站建設(shè)方案服務(wù)
  • 做網(wǎng)站必須要購(gòu)買空間嗎谷歌瀏覽器 免費(fèi)下載
  • 網(wǎng)頁(yè)編輯軟件中文版seo英文全稱
  • 外貿(mào)怎么做網(wǎng)站外鏈seo網(wǎng)站結(jié)構(gòu)優(yōu)化的方法
  • 做調(diào)查賺錢網(wǎng)站有哪些網(wǎng)站推廣
  • 怎么讓網(wǎng)站能被百度到互聯(lián)網(wǎng)營(yíng)銷師考試
  • 網(wǎng)站建設(shè)經(jīng)驗(yàn)分享google adsense
  • 搜狗新聞源網(wǎng)站怎么做云南seo公司
  • 江寧網(wǎng)站建設(shè)要多少錢新聞小學(xué)生摘抄
  • wordpress 圖片在哪威海百度seo
  • 如何用魔方網(wǎng)表做門戶網(wǎng)站真正免費(fèi)的建站
  • 網(wǎng)站怎么做圖片網(wǎng)絡(luò)營(yíng)銷的特征和功能
  • 吉安網(wǎng)站設(shè)計(jì)杭州百度優(yōu)化
  • 濟(jì)南集團(tuán)網(wǎng)站建設(shè)公司百度快照如何優(yōu)化
  • 制作英文網(wǎng)站費(fèi)用營(yíng)銷策略分析
  • 寺院網(wǎng)站建設(shè)谷歌網(wǎng)站收錄提交入口
  • 大型門戶網(wǎng)站開發(fā)費(fèi)用發(fā)稿媒體平臺(tái)
  • 網(wǎng)站死鏈怎么刪除seo管理系統(tǒng)
  • 西安南郊網(wǎng)站建設(shè)seo 優(yōu)化技術(shù)難度大嗎
  • 試述網(wǎng)站建設(shè)應(yīng)考慮哪些方面的問題競(jìng)價(jià)排名的定義
  • 中小企業(yè)網(wǎng)站建設(shè)中服務(wù)器的解決方案是找客戶資源的軟件哪個(gè)最靠譜
  • 網(wǎng)絡(luò)建站公司如何做市場(chǎng)網(wǎng)站營(yíng)銷與推廣
  • wordpress獲取當(dāng)前分類名稱seo軟件資源
  • 網(wǎng)站建設(shè) 2018網(wǎng)站設(shè)計(jì)與制作教程
  • 重慶旅游網(wǎng)站制作公司百度搜索風(fēng)云榜手機(jī)版