題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)由n個(gè)數(shù)字組成的數(shù)列，現(xiàn)在給出規(guī)則是，每次選擇數(shù)列中的一種數(shù)字 x，選擇后的貢獻(xiàn)為 x，不過操作后會刪除掉所有數(shù)值為 x + 1 和 x - 1 的數(shù)，現(xiàn)在問如何選擇可以使得貢獻(xiàn)最大

題目分析：線性dp，因?yàn)槊總€(gè)數(shù)若選擇的話，那么他前后兩個(gè)數(shù)都無法選擇了，我們可以直接視為相鄰兩個(gè)數(shù)的關(guān)系，若當(dāng)前的數(shù)選了，那么前一個(gè)數(shù)就沒法選，若當(dāng)前的數(shù)不選，則前一個(gè)數(shù)是可以選的，雖然這樣無法限制到后面的那個(gè)數(shù)，但是隨著狀態(tài)的轉(zhuǎn)移，到達(dá)后一個(gè)數(shù)時(shí)的決策和前面的決策并不會沖突，所以dp[i]代表選擇數(shù)字 i 的最大貢獻(xiàn)，那么轉(zhuǎn)移方程就是：

dp[i]=max(dp[i-1],dp[i-2]+num*cnt[num])，i代表的是數(shù)值，范圍為[1,1e5]

cnt數(shù)組是每個(gè)數(shù)字出現(xiàn)的次數(shù)，維護(hù)好所需要的信息后，直接轉(zhuǎn)移就好了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int cnt[N];LL dp[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){int num;scanf("%d",&num);cnt[num]++;}LL ans=0;dp[1]=cnt[1];for(int i=1;i<N;i++){dp[i]=max(dp[i-2]+1LL*i*cnt[i],dp[i-1]);ans=max(ans,dp[i]);}printf("%lld\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 456C Boredom(线性dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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