头像

SinclairWang


访客:177

离线:2小时前



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]

include[HTML_REMOVED]

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;
}

``



活动打卡代码 AcWing 282. 石子合并

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;
}


活动打卡代码 AcWing 3. 完全背包问题

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;
}


活动打卡代码 AcWing 2. 01背包问题

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;
}