最大上升子序列和最大上升子序列的和
2026-01-10 17:44:32
发布于：广东
7阅读
0回复
0点赞
//树状数组
//求x,y坐标3*3的sum
//最大上升子序列
//ans[i]记住以a[i]结尾的最长上升子序列的长度
//1 7 3 5 9 4 8
//1 2 2 3 4 3 4
//最大上升子序列和
//1 7 3 5 9 4 8
//1 8 4 9
//ans[i]记住以a[i]结尾的上升子序列的最大和
//记忆化和状态转移方程
//n个物品,m种
//要求每种买一个,总价格最小
//记忆化
//ans[i] --->将第i种物品的最小价格记住
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
int ans[N];//记录第i种物品的最小价格
void solve(){
int n,m;
cin>>m>>n;
for(int i=1;i<=m;i++)ans[i]=N;//
for(int i=1;i<=n;i++){
int k,p;
cin>>k>>p;
ans[k]=min(ans[k],p);
}
int res=0;
for(int i=1;i<=m;i++){
if(ans[i]!=N){
res+=ans[i];
}
}
cout<<res<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
这里空空如也
有帮助，赞一个