2020.6.21
2020.6.21
2020.6.21考完月考的第一天還沒出成績 趕緊來加一篇
d
p
dp
dp
2020.10.13
2020.10.13
2020.10.13沒報上
C
S
P
CSP
CSP要考聯賽得用老師的推薦名額，所以趕緊回來好好學兩個月拿個一等獎
現在就啥對聯賽有用就學啥，先弄
d
p
dp
dp，再弄圖論，最后整點數奆結垢和數學
先可簡單的整吧
基本概念
大家應該都知道線性 d p dp dp，即在線性結構上進行狀態轉移，而區間類動態規劃是線性動態規劃的拓展，它在分階段劃分問題時，與階段中元素出現的順序和由前一階段哪些元素合并而來有很大的關系，如狀態 f [ i ] [ j ] f[i][j] f[i][j]，它表示以 已合并的次數為階段， 以 區卷左端點 i i i為狀態，它的值取決于第 i i i個元素和第 j j j個元素斷開的位置 k k k，即 f [ i ] [ k ] + f [ k + 1 ] [ j ] f[i][k]+f[k+1][j] f[i][k]+f[k+1][j]的值，這一型別的動態規劃，階段特征得長明顯，求最優值時需要預先設定階段內的區間統計值，還要以動態規劃的起始位置來判斷，
操作
區間
d
p
dp
dp一般只有兩步操作
1.
1.
1.合并：即將兩個或多個部分進行整合，當然也可以反過來，也就是對一個問題分解成兩個或多個部分
2.
2.
2.求解：對整個問題設最優值，列舉合并點，將問題分解成左右兩個部分，最后合并左右兩個部分得最優值得到原問題的最優值，類似分治演算法的思想，
所以一個問題能不能用區間 d p dp dp，就是要看這個問題是否能被分解成為兩兩合并的形式，
這塊也沒啥難的 直接上題
石子合并
題面
S
o
l
u
t
i
o
n
:
Solution:
Solution:這題做的時候注意一下石頭是按圓形操場擺放的 不是排一排
那怎么轉化為排成一排的呢 只需要把序列再復制一遍就可以了
轉移方程根本不用推，，
最大時
d
p
[
i
]
[
j
]
=
m
i
n
k
=
i
j
?
1
{
d
p
[
i
]
[
k
]
+
d
p
[
k
+
1
]
[
j
]
+
∑
l
=
i
j
a
[
l
]
}
dp[i][j]=min_{k=i}^{j-1}\{dp[i][k]+dp[k+1][j]+\sum_{l=i}^{j}a[l]\}
dp[i][j]=mink=ij?1?{dp[i][k]+dp[k+1][j]+∑l=ij?a[l]}
最小時
d
p
[
i
]
[
j
]
=
m
a
k
=
i
j
?
1
{
d
p
[
i
]
[
k
]
+
d
p
[
k
+
1
]
[
j
]
+
∑
l
=
i
j
a
[
l
]
}
dp[i][j]=ma_{k=i}^{j-1}\{dp[i][k]+dp[k+1][j]+\sum_{l=i}^{j}a[l]\}
dp[i][j]=mak=ij?1?{dp[i][k]+dp[k+1][j]+∑l=ij?a[l]}
上代碼:
#include<bits/stdc++.h>
using namespace std;
#define N 404
#define maxx 999999999
int n,ans,a[N],s[N],dp[N][N];
inline void read(int &x){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
x=s*w;
}
int main(){
read(n);
for(int i=1;i<=n;i++)read(a[i]),a[i+n]=a[i];
for(int i=1;i<=n<<1;i++)s[i]=s[i-1]+a[i];
for(int l=1;l<n;l++){
for(int i=1,j=l+1;j<=n<<1;i++,j++){
dp[i][j]=maxx;
for(int k=i;k<j;k++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
}
}
ans=maxx;
for(int i=1;i<=n;i++)ans=min(dp[i][i+n-1],ans);
printf("%d\n",ans);
for(int l=1;l<n;l++){
for(int i=1,j=l+1;j<=n<<1;i++,j++){
dp[i][j]=0;
for(int k=i;k<j;k++)dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
}
}
ans=0;
for(int i=1;i<=n;i++)ans=max(dp[i][i+n-1],ans);
printf("%d\n",ans);
}
能量項鏈
題面
S
o
l
u
t
i
o
n
:
Solution:
Solution:果題 需要注意的是
i
?
k
i-k
i?k區間和
k
?
j
k-j
k?j區間合并時 加上的是
a
[
i
]
×
a
[
k
+
1
]
×
a
[
j
+
1
]
a[i]×a[k+1]×a[j+1]
a[i]×a[k+1]×a[j+1] 別乘錯了！
狀態轉移方程:
d
p
[
i
]
[
j
]
=
m
a
x
k
=
i
j
?
1
{
d
p
[
i
]
[
k
]
+
d
p
[
k
]
[
j
]
+
a
[
i
]
×
a
[
k
+
1
]
×
a
[
j
+
1
]
}
dp[i][j]=max_{k=i}^{j-1}\{dp[i][k]+dp[k][j]+a[i]×a[k+1]×a[j+1]\}
dp[i][j]=maxk=ij?1?{dp[i][k]+dp[k][j]+a[i]×a[k+1]×a[j+1]}
代碼↓
#include<bits/stdc++.h>
using namespace std;
#define N 220
int n,ans,a[N],dp[N][N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(int l=1;l<n;l++){
for(int i=1,j=l+1;j<=n<<1;i++,j++){
for(int k=i;k<j;k++)dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]);
}
}
for(int i=1;i<=n;i++)if(dp[i][i+n-1]>ans)ans=dp[i][i+n-1];
printf("%d\n",ans);
}
凸多邊形的劃分
題目描述
給定一個具有N(N≤50)個頂點(從1到N編號)的凸多邊形，每個頂點的權均是一個正整教，
問:如何把這個凸多邊形劃分成N-2個互不相交的三角形，使得這些三角形頂點的權的乘積之和最小?
輸入
輸入檔案的第一一行為頂點數N;第二行為N個頂點(從1到N)的權值，
輸出
輸出一行為這些三角形頂點的權的乘積之和的最小值，
樣例輸入
5
121 122 123 245 231
樣例輸出
12214884
提示
S
o
l
u
t
i
o
n
:
Solution:
Solution:
先將節點順時針依次編號
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]表示從
i
i
i節點到
j
j
j節點劃分得到的乘積之和最小值
如圖
那么如何狀態轉移呢
設
k
∈
(
i
,
j
)
k∈(i,j)
k∈(i,j)，將
i
?
j
i-j
i?j分成
i
?
k
,
k
?
j
i-k,k-j
i?k,k?j來轉移
如圖，在
k
k
k點分割之后出現了三個三角形
綠色部分分別為
d
p
[
i
]
[
k
]
dp[i][k]
dp[i][k]和
d
p
[
k
]
[
j
]
dp[k][j]
dp[k][j]
黃色部分為
a
[
i
]
×
a
[
j
]
×
a
[
k
]
a[i]×a[j]×a[k]
a[i]×a[j]×a[k]
那么
d
p
[
i
]
[
j
]
=
m
i
n
k
=
i
+
1
j
?
1
{
d
p
[
i
]
[
k
]
+
d
p
[
k
]
[
j
]
+
a
[
i
]
×
a
[
j
]
×
a
[
k
]
}
dp[i][j]=min_{k=i+1}^{j-1}\{dp[i][k]+dp[k][j]+a[i]×a[j]×a[k]\}
dp[i][j]=mink=i+1j?1?{dp[i][k]+dp[k][j]+a[i]×a[j]×a[k]}
初始狀態
d
p
[
i
]
[
j
]
=
m
a
x
dp[i][j]=max
dp[i][j]=max，
d
p
[
i
]
[
i
+
1
]
=
0
dp[i][i+1]=0
dp[i][i+1]=0
需要注意的是不開高精只有50分
q
a
q
qaq
qaq
就當打高精模板了
上代碼
#include<bits/stdc++.h>
using namespace std;
#define N 55
#define ll long long
ll n,a[N];
struct bigint{
int len,s[303];
bigint(){
memset(s,0,sizeof(s));
len=1;
}
bool operator <(const bigint &A)const{
if(len!=A.len)return len<A.len;
for(int i=len-1;~i;i--)
if(s[i]!=A.s[i])return s[i]<A.s[i];
return false;
}
bigint operator +(const bigint &A)const{
bigint B;
B.len=max(len,A.len);
for(int i=0;i<B.len;i++){
B.s[i]+=s[i]+A.s[i];
B.s[i+1]+=B.s[i]/10,B.s[i]%=10;
}
if(B.s[B.len])B.len++;
return B;
}
bigint operator *(const bigint &A)const{
bigint B;
B.len=len+A.len-1;
for(int i=0;i<A.len;i++){
for(int j=0;j<len;j++){
B.s[i+j]+=A.s[i]*s[j];
B.s[i+j+1]+=B.s[i+j]/10,B.s[i+j]%=10;
}
}
if(B.s[B.len])B.len++;
return B;
}
void print(){
int now=len-1;
while(!s[now]&&now)now--;
for(int i=now;~i;i--)printf("%d",s[i]);
}
}dp[N][N];
bigint change(ll x){
bigint t;int cnt=0;
while(x){
t.s[cnt++]=x%10;
x/=10;
}
t.len=cnt;
return t;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int l=2;l<n;l++){
for(int i=1,j=l+1;j<=n;i++,j++){
dp[i][j].len=300,dp[i][j].s[299]=1;
for(int k=i+1;k<j;k++){
bigint t=change(a[i])*change(a[j])*change(a[k]);
bigint newdp=dp[i][k]+dp[k][j]+t;
if(newdp<dp[i][j])dp[i][j]=newdp;
}
}
}
dp[1][n].print();
}
括號配對
題面
S
o
l
u
t
i
o
n
:
Solution:
Solution:判斷需要最少加幾個括號就是找最少有多少個括號沒匹配
逆向思維直接找能匹配的最多的括號
可以直接用
S
T
L
STL
STL堆疊過 還是練下區間
d
p
dp
dp吧
用
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]表示
i
?
j
i-j
i?j區間內可以匹配到的最大括號數量
在序列
i
?
j
i-j
i?j中 如果
s
[
i
]
s[i]
s[i]和
s
[
j
]
s[j]
s[j]可以匹配，則
d
p
[
i
]
[
j
]
=
d
p
[
i
+
1
]
[
j
?
1
]
+
2
dp[i][j]=dp[i+1][j-1]+2
dp[i][j]=dp[i+1][j?1]+2
之后再直接判斷
d
p
[
i
]
[
j
]
=
m
a
x
k
=
i
j
?
1
{
d
p
[
i
]
[
k
]
+
d
p
[
k
]
[
j
]
}
dp[i][j]=max_{k=i}^{j-1}\{dp[i][k]+dp[k][j]\}
dp[i][j]=maxk=ij?1?{dp[i][k]+dp[k][j]}
上代碼
#include<bits/stdc++.h>
using namespace std;
int n,dp[110][110];
char s[110];
int main(){
gets(s);
n=strlen(s);
for(int l=1;l<n;l++){
for(int i=0,j=l;j<n;i++,j++){
if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']'))dp[i][j]=dp[i+1][j-1]+2;
for(int k=i;k<j;k++)dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
cout<<n-dp[0][n-1]<<endl;
}
分離與合體
題面
S
o
l
u
t
i
o
n
:
Solution:
Solution:這題題面不太好懂，先看第一問，大概意思就是說一個序列，每兩個數可以合并成一個數，問最后合并的數最大是多少
很顯然的區間
d
p
dp
dp，轉移方程一眼就能看出來
d
p
[
i
]
[
j
]
=
m
a
x
k
=
i
j
?
1
{
d
p
[
i
]
[
k
]
+
d
p
[
k
?
1
]
[
j
]
+
(
a
[
i
]
+
a
[
j
]
)
×
a
[
k
]
}
dp[i][j]=max_{k=i}^{j-1}\{dp[i][k]+dp[k-1][j]+(a[i]+a[j])×a[k]\}
dp[i][j]=maxk=ij?1?{dp[i][k]+dp[k?1][j]+(a[i]+a[j])×a[k]}
但是問題是第二問，如何將每次分裂記下來
設
p
[
i
]
[
j
]
p[i][j]
p[i][j]是
i
i
i到
j
j
j區間分裂的位置，只需在每次更新
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]時順便維護
p
p
p陣列
即當
d
p
[
i
]
[
k
]
+
d
p
[
k
?
1
]
[
j
]
+
(
a
[
i
]
+
a
[
j
]
)
×
a
[
k
]
>
d
p
[
i
]
[
j
]
dp[i][k]+dp[k-1][j]+(a[i]+a[j])×a[k]>dp[i][j]
dp[i][k]+dp[k?1][j]+(a[i]+a[j])×a[k]>dp[i][j]時 讓
p
[
i
]
[
j
]
=
k
p[i][j]=k
p[i][j]=k即可
輸出時用搜索來找每一層分裂的位置，因為除第一層外有很多個分裂點，所以用
v
e
c
t
o
r
vector
vector來存盤每一層分裂的位置，最后再排序輸出
需要注意的是 最后一個數不要輸出空格 不然會格式錯誤…
上代碼
#include<bits/stdc++.h>
using namespace std;
#define N 330
int n,dep,a[N],dp[N][N],p[N][N];
vector<int> ans[N];
void dfs(int l, int r, int depth){
if(l==r)return ;
if(depth>dep)dep=depth;
ans[depth].push_back(p[l][r]);
dfs(l,p[l][r],depth+1);
dfs(p[l][r]+1,r,depth+1);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int l=1;l<n;l++){
for(int i=1,j=l+1;j<=n;i++,j++){
for(int k=i;k<j;k++){
int now=dp[i][k]+dp[k+1][j]+(a[i]+a[j])*a[k];
if(now>dp[i][j])dp[i][j]=now,p[i][j]=k;
}
}
}
cout<<dp[1][n]<<endl;
dfs(1,n,1);
for(int i=1;i<=dep;i++)sort(ans[i].begin(),ans[i].end());
for(int i=1;i<=dep;i++){
int siz=ans[i].size();
for(int j=0;j<siz;j++){
if(j==siz-1&&i==dep)printf("%d",ans[i][j]);
else printf("%d ",ans[i][j]);
}
}
cout<<endl;
}
矩陣取數游戲
題面
S
o
l
u
t
i
o
n
:
Solution:
Solution:這題還是個
N
O
I
P
NOIP
NOIP題哈哈
每行取的數只與本行之前的方案有關，所以我們只需要讓每一行都取最優
設
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]表示每行處理
i
?
j
i-j
i?j時，當前的最優方案
則
d
p
[
i
]
[
j
]
=
m
a
x
{
d
p
[
i
?
1
]
[
j
]
+
2
m
?
i
?
j
+
1
,
d
p
[
i
]
[
j
+
1
]
+
2
m
?
i
?
j
+
1
}
dp[i][j]=max\{dp[i-1][j]+2^{m-i-j+1},dp[i][j+1]+2^{m-i-j+1}\}
dp[i][j]=max{dp[i?1][j]+2m?i?j+1,dp[i][j+1]+2m?i?j+1}
答案需要在區間為
1
1
1的
d
p
[
i
]
[
i
]
dp[i][i]
dp[i][i]里找
a
n
s
=
∑
k
=
1
n
m
a
x
i
=
1
m
{
d
p
[
i
]
[
i
]
+
2
i
×
a
[
i
]
}
ans=\sum\limits_{k=1}^{n}max_{i=1}^{m}\{dp[i][i]+2^i×a[i]\}
ans=k=1∑n?maxi=1m?{dp[i][i]+2i×a[i]}
預處理出
2
n
2^n
2n，再打個高精 就可以了
代碼在機房 不想再打一次高精了
(
(
(哭哭 周二更代碼
周一中午跑來交代碼了哈哈 我
D
a
w
n
Dawn
Dawn絕不鴿！
上代碼↓
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define N 82
struct bigint{
int s[301],len;
bigint(){
memset(s,0,sizeof(s));
len=1;
}
bool operator <(const bigint &A)const{
if(len!=A.len)return len<A.len;
for(reg int i=len-1;~i;i--)
if(s[i]!=A.s[i])return s[i]<A.s[i];
return false;
}
bigint operator +(const bigint &A)const{
bigint B;
B.len=max(len,A.len);
for(int i=0;i<B.len;i++)
B.s[i]+=s[i]+A.s[i],B.s[i+1]+=B.s[i]/10,B.s[i]%=10;
if(B.s[B.len])B.len++;
return B;
}
bigint operator *(const bigint &A)const{
bigint B;
B.len=len+A.len-1;
for(int i=0;i<A.len;i++)
for(int j=0;j<len;j++)
B.s[i+j]+=A.s[i]*s[j],B.s[i+j+1]+=B.s[i+j]/10,B.s[i+j]%=10;
if(B.s[B.len])B.len++;
return B;
}
void print(){
int now=len-1;
while(!s[now]&&now)now--;
for(reg int i=now;~i;i--)putchar(s[i]+'0');
putchar(10);
}
}dp[N][N],bas[N],cnt;
void work(){
bas[0].len=1,bas[0].s[0]=1;
bigint t;t.len=1,t.s[0]=2;
for(reg int i=1;i<=80;i++)bas[i]=bas[i-1]*t;
}
bigint change(int x){
int sum=0;
bigint num;
while(x){
num.s[sum++]=x%10;
x/=10;
}
num.len=sum;
return num;
}
int n,m,a[N];
int main(){
cin>>n>>m;
work();
for(reg int f=1;f<=n;f++){
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++)
dp[i][j].len=1,dp[i][j].s[0]=0;
}
for(reg int i=1;i<=m;i++)scanf("%d",&a[i]);
for(reg int i=1;i<=m;i++)
for(reg int j=m;j>=i;j--){
bigint p=change(a[i-1]),q=change(a[j+1]);
bigint s1=dp[i-1][j]+p*bas[m+i-j-1],s2=dp[i][j+1]+q*bas[m-j+i-1];
if(dp[i][j]<s1)dp[i][j]=s1;
if(dp[i][j]<s2)dp[i][j]=s2;
}
bigint ans;
for(reg int i=1;i<=m;i++){
bigint p=change(a[i]);
if(ans<p*bas[m]+dp[i][i])ans=p*bas[m]+dp[i][i];
}
cnt=cnt+ans;
}
cnt.print();putchar(10);
}
總結
區間 d p dp dp的復雜度一般都是 O ( n 3 ) O(n^3) O(n3)，故資料范圍在 100 100 100左右時可以考慮區間 d p dp dp，區間 d p dp dp的狀態轉移方程好想，總體來說是個不錯的解題方法，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/192168.html
標籤：python