2024/4/11

知识

埃氏筛

题目

T1 P1832 A+B Problem（再升级）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include<bits/stdc++.h>
using namespace std;
bool isprime[100001];
long long dp[100001],n;
void getprime(){
	memset(isprime,true,sizeof(isprime));
	for(int i=2;i*i<=n;i++){
		if(isprime[i]==true){
			for(int j=i*i;j<=n;j+=i){
				isprime[j]=false;
			}
		} 
	}
}
int main(){
	cin>>n;
	dp[0]=1;
	getprime();
	for(int i=2;i<=n;i++){
		if(isprime[i]){
			for(int j=i;j<=n;j++){
				dp[j]+=dp[j-i];
			}
		}
	}
	cout<<dp[n];
	return 0;
} 

P1853 投资的最大效益

#include<bits/stdc++.h>
using namespace std;
const int sss=1e7+5;
int dp[sss],a[10001],b[10001];
int n,s,d;
int main(){
    cin>>n>>s>>d;
    for(int i=1;i<=d;i++) cin>>a[i]>>b[i];
    for(int i=1;i<=n;i++){
        for(int j=1;i<=d;j++){
            for(int k=a[j];k<=s;k++){
                dp[k]=max(dp[k],dp[k-a[j]]+b[j]); 
            }
        }
        s+=dp[s];//本金++ 
    }
    cout<<s;
}
```cpp
#include<bits/stdc++.h>
using namespace std;
const int sss=1e7+5;
int dp[sss],a[10001],b[10001];
int n,s,d;
int main(){
    cin>>n>>s>>d;
    for(int i=1;i<=d;i++) cin>>a[i]>>b[i];
    for(int i=1;i<=n;i++){
        for(int j=1;i<=d;j++){
            for(int k=a[j];k<=s;k++){
                dp[k]=max(dp[k],dp[k-a[j]]+b[j]); 
            }
        }
        s+=dp[s];//本金++ 
    }
    cout<<s;
}