前言

$\%$一下出題人$BPM$

---

正題

題目鏈接:https://www.luogu.com.cn/problem/U102488

---

題目大意

$n$個(gè)數(shù)，選取兩組(不一定要全用上)使得他們的和相等且最大。

---

解題思路

考慮$dp$，$f_{i,j}$表示到第$i$個(gè)，差值為$j$(這里的差值是大的減去小的)。

然后有

不選$$f_{i,j}=f_{i?1,j}$$

加在大的那個(gè)上
$$f_{i,j+a_i}=f_{i?1,j}+a_i$$

加在小的那個(gè)上
$$f_{i,|j?a_i|}=f_{i?1,j}+max\{a_i?j,0\}$$

時(shí)間復(fù)雜度$O(n^2)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=5100; int n,a[N],f[N][N]; int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);memset(f,0xcf,sizeof(f));f[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=5000;j++){f[i][j]=max(f[i][j],f[i-1][j]);f[i][j+a[i]]=max(f[i][j+a[i]],f[i-1][j]+a[i]);f[i][abs(j-a[i])]=max(f[i][abs(j-a[i])],f[i-1][j]+max(a[i]-j,0));}}printf("%d",f[n][0]); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的U102488-傻叉题【dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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