SinclairWang

SinclairWang
1个月前
class Solution {
public:
unordered_map<int,int> hash;
int dfs(int n){
if(n==1) return 1;
if(hash[n]!=0) return hash[n];
// 定义该子问题的结果
int res = n; // 最坏情况是每天吃一个
if(n%3==0)  res = min(res,dfs(n/3)+1);
if(n%2==0) res = min(res,dfs(n/2)+1);
// 如果能被6整除,就不尝试-1的情况,算是剪枝,不然会TLE
if(n%6) res = min(res,dfs(n-1)+1);
hash[n] = res;
return res;
}
int minDays(int n) {
return dfs(n);
}
};


SinclairWang
1个月前
class Solution {
public:
int minOperations(int n) {
return n*n/4;
}
};


SinclairWang
1个月前
class Solution {
public:
int maxDistance(vector<int>& pos, int m) {
sort(pos.begin(),pos.end());  // pos数组可能是无序的,需要排序
int l = 0, r = 1e9;
while(l<r){
int mid = l+r+1 >>1;
int count = 1,last = pos[0];
for(int i=1;i<pos.size();i++){
if(pos[i]-last>=mid) count ++,last = pos[i];
}
if(count>=m) l = mid;
else r = mid-1;
}
return l;
}
};


SinclairWang
1个月前
class Solution {
public:
bool threeConsecutiveOdds(vector<int>& arr) {
for(int i=0;i+2<arr.size();i++){
if(arr[i]%2&&arr[i+1]%2&&arr[i+2]%2) return true;
}
return false;
}
};



SinclairWang
5个月前

cpp

include[HTML_REMOVED]

using namespace std;
const int maxn = 1010;
int n,m;
int dp[maxn][maxn];
char a[maxn],b[maxn];
int main(){
cin >> n >> m;
cin >> a+1;
cin >> b+1;
for(int i=1;i<=n;i){
for(int j=1;j<=m;j
){
if(a[i]==b[j]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
}
}
cout << dp[n][m];
return 0;
}



SinclairWang
5个月前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int maxn = 310, INF = 1e9;
int w[maxn],s[maxn],n;
int dp[maxn][maxn];

int main(){
cin >> n;
for(int i=1;i<=n;i++) cin >> w[i];
for(int i=1;i<=n;i++) s[i] = s[i-1]+w[i];
for(int len = 2;len<=n;len++){
for(int l = 1;l+len-1<=n;l++){
int r = l+len-1;
dp[l][r] = INF;
for(int k=l;k<r;k++){
dp[l][r] = min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
}
}
}
cout << dp[1][n];
return 0;
}


SinclairWang
5个月前
#include<iostream>
#include<algorithm>

using namespace std;
const int maxn = 1010;
int w,v,n,m,k;
int dp[maxn];
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> v >> w;
for(int j=m;j>=v;j--){
for(int k = 0;k*v<=j;k++){
dp[j] = max(dp[j],dp[j-k*v]+k*w);
}
}
}
cout << dp[m];
return 0;
}


SinclairWang
5个月前
#include <iostream>

using namespace std;
const int maxn = 1010;
int n,m;
int f[maxn][maxn],w[maxn],v[maxn];

int main(){
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
f[i][j] = f[i-1][j];
if(j>=v[i])f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}
`