先做简单的数据处理,合并相同的数字,然后可以当成偷盗问题
#include <iostream> #include <vector> using namespace std; int main() { //ai<10^4 int n,t,i; cin>>n; vector<int> items; while(n-- && cin>>t){ if(t+1>items.size())items.resize(t+1,0); items[t]+=t; } vector<int> dp(items.size(),0); dp[1]=items[1];//避免每次循环都判断i有没有大于1,直接做了 for(int i=2;i<dp.size();i++){ dp[i]=max(dp[i-1],dp[i-2]+items[i]); } //printa(items); // printa(dp); cout<<dp[dp.size()-1]<<endl; } // 64 位输出请用 printf("%lld")