2024-04-12竞赛笔记

2024/4/12

知识

最长上升子序列

#include<bits/stdc++.h>
using namespace std;
int a[100001],f[100001];
int main(){
	int n,ans;
	cin>>n;
	for(int i=1;i<=n;i++){
		f[i]=1;
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i]>a[j]){
				f[i]=max(f[i],f[j]+1);
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,f[i]);
	}
	cout<<ans;
	return 0;
}

题目

T1 P1853 投资的最大效益

#include<bits/stdc++.h>
using namespace std;
int k/*总共消耗的邮票数*/,n,s; 
const int N=2e6,M=1e2,INF=0x3f3f3f3f;
int a[M],f[N];//f[i]表示构成面值为i至少需要的you票数 
signed main(){
	cin>>k>>n;
	memset(f,INF,sizeof(f));
	f[0]=0;//初始值
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=a[i];j<=N;j++){
			if(f[j-a[i]]+1<=k){//在限制使用的范围内 
				f[j]=min(f[j],f[j-a[i]]+1);//min的 
			}
		}
	} 
	s=0;
	for(int i=1;i<=N;i++){
		if(f[i]==INF){ //找不出了 
			s=i-1;//记录 
			break;
		}
	}
	cout<<s<<endl;
	return 0;
}