倒推消除后效性，dp有贪心的形
类似背包，正着推不知道选和不选谁更优
倒着递推消除前面的影响
以后当前状态对后面有影响时，可以倒着推，消除后效性
dp有贪心的形，如最大、最小等
#include<bits/stdc++.h>
using namespace std;
int const N=1e4+7;
int n,k;
vector<int>v[N];
int f[N];
int main(){
cin >> n >> k;
for(int i=1;i<=k;++i){
int a,b;cin >> a >> b;
v[a].push_back(b);
}
for(int i=n;i>=1;--i){
if(v[i].size()){
for(int j=0;j<v[i].size();++j){
f[i]=max(f[i],f[i+v[i][j]]);
}
}
else f[i]=f[i+1]+1;
}
cout << f[1];
return 0;
}
查看9道真题和解析
