头像

屎前巨饿




离线:9小时前


活动打卡代码 AcWing 1163. 纪念品

屎前巨饿
9小时前

题意:
能预测未来的价格变化, 当前有m个金币,问 最后最多能拿到多少金币;

首先我们明白一个问题
        第一天买下                           第三天卖出
等于    第一天买下,第二天卖出,第二天买下, 第三天卖出
我们明白这个是等价的, 再观察问题,这么多天求最大值, 然后有容量m 并且可以无限购买
可以等价成完全背包问题 最大价值

神奇吧
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
ll a[maxn];
ll t, n, m;
ll w[1001][1001]; // 表示第i天的 第j个物品的价格
ll f[maxn]; // 递推公式
            //  f[i] = max(f[i], f[i] )

int main()
{
    cin >> t >> n >> m;
    for(int i = 1; i <= t; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            cin >> w[i][j]; // day price
        }
    }

    // wan quan bei bao

    for(int i = 1; i < t; i ++) // day
    {
        memset(f, 0, sizeof f);
        for(int j = 1; j <= n; j ++) // object
        {
            if(w[i+1][j] > w[i][j]) // win
            {
                for(int k = w[i][j]; k <= m; k ++)
                {
                    f[k] = max(f[k], f[k-w[i][j]] + w[i+1][j]-w[i][j]);
                }
            }
        }
        m += f[m];
    }
//  cout << "___" << endl;
//  cout << m << endl;
    printf("%d\n",m);
    return 0;
}


活动打卡代码 AcWing 1162. 公交换乘

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
ll n, price[maxn] ,t[maxn];

int main()
{
    cin >> n;
    ll ans = 0;
    vector<pair<ll, ll> > ve;
    ll l = 0;
    for(int i = 1; i <= n; i ++)
    {
        ll a, price[i], t[i];
        cin >> a >> price[i] >> t[i];

        if(a == 0)
        {
            ve.push_back({price[i], t[i]});
            ans += price[i];
        }
        else
        {
            bool is = false;
            for(int j = l; j < ve.size(); j ++)
            {
                if(t[i] -ve[j].second >= 45) l ++;
                if(ve[j].first == -1) continue;
                if(ve[j].first < price[i]) continue;

                if(t[i] - ve[j].second <= 45)
                {
                    is = true;
                    ve[j].first = -1;
                    break;
                }
            }

            if(!is)
            {
                ans += price[i];
            }
        }   
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 901. 滑雪

要求: 滑雪到每个比当前位置小的位置
我们正常的dfs 是会超时的 这个可以理解

所以我们的想法就是,更新每个位置,可以划过来的最大长度

状态划分
2222.png

这里忘了加一了 。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
ll r, c;
ll mp[330][330];
ll f[330][330];
ll dx[4] = {1,0,-1, 0};
ll dy[4] = {0,-1,0,1};
ll num = 0;
ll maxi = -1;

ll dfs(ll x, ll y)
{
    if(f[x][y] != 0) return f[x][y];

    for(int i = 0; i < 4; i ++)
    {
        int x1 = x+dx[i];
        int y1 = y+dy[i];

        if(x1>=1&&x1<=r&&y1>=1&&y1<=c&&mp[x1][y1]<mp[x][y])
        {
            f[x][y] = max(f[x][y], dfs(x1, y1)+1);
        }
    }
    return f[x][y];
}

int main()
{
    cin >> r >> c;
    for(int i = 1; i <= r; i ++)
    {
        for(int j = 1; j <= c; j ++)
        {
            cin >> mp[i][j];
        }
    }

    for(int i =1;  i<= r; i ++)
    {
        for(int j = 1; j <= c; j ++)
        {
            maxi = max(maxi, dfs(i,j));
        }
    }

    cout << maxi+1 << endl;
    return 0;
}



n 问有多少种,可能能正好组成n
那么就可以看成是有1 到n数字每个都是无限的,组合有多少种方案可以组合成n, 即为完全背包问题。

完全背包优化问题:
f[i][j] = f[i-1][j]+ f[i-1][j-1] + f[i-1][j-i2]..f[i-1][j-is];
f[i][j-1]= f[i-1][j-1] + f[i-1][j-i2]..f[i-1][j-is];

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
const int mod = 1e9+7;
ll n;
int f[1010];

int main()
{
    cin >> n;

    f[0] = 1;
    for(int i = 1; i <= n; i ++) //枚举从1到n所有的物品
    {
        for(int j = i; j <= n; j ++) // 枚举所有的容积
        {
            f[j] = (f[j] + f[j-i])%mod; //方案数
        }
    }

    cout << f[n] << endl;
    return 0;
}



石子合并
所谓区间dp 就是枚举的区间 从小区间到大区间,依次推导

11111.png

#include<bits/stdc++.h>
#include<string.h>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
const ll mod = 1e9+7;
ll n, m;
ll a[maxn], sum[maxn];
ll f[2000][2000];

int main()
{
    cin >> n;
    memset(f, 0x3f, sizeof f);// 先将区间设置为无穷大因为要求min
    for(int i = 1; i <= n; i ++)
    {
        ll x;
        cin >> x;
        sum[i] = sum[i-1] + x;// 求区间合并的值, 所以用前缀和来当作价值
        f[i][i] = 0;
    }

    for(int len = 2; len <= n; len ++)枚举,区间的长度
    {
        for(int l = 1; l+len-1 <= n; l ++) // 枚举左端点
        {
            int r = l+len-1; //设置右端点的
            for(int k = l; k < r; k ++) // 枚举中间的断点
            {
                f[l][r] = min(f[l][r], f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
            }
        }
    }

    cout << f[1][n] << endl;
    return 0;
}



编辑距离:
利用上一个题的最短操作, 每个遍历一次dp就好了

#include<bits/stdc++.h>
#include<string.h>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
const ll mod = 1e9+7;
ll n, m;
int f[20][20];
char a[1005][16];

int dis(char a[], char b[])
{
    int la = strlen(a+1);
    int lb = strlen(b+1);

    for(int i = 0; i <= la; i ++) f[i][0] = i; //要记得初始化
    for(int i = 0; i <= lb; i ++) f[0][i] = i;

    for(int i = 1; i <= la; i ++)
    {
        for(int j = 1; j <= lb; j ++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
    }
    return f[la][lb];
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 0; i < n; i ++)
    {
        scanf(" %s",a[i]+1); //用数组来存字符串
    }
    while(m --)
    {
        char b[1050];
        int sum;
        scanf(" %s",b+1);
        scanf(" %d",&sum);

        ll ans = 0;
        for(int i = 0; i < n; i ++)
        {
            if(dis(a[i], b) <= sum)
            {
                ans ++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}



编辑最短距离:
操作: ①: 增加一个字母
②:删除一个字母
③:修改一个字母

问 将长度为n的a字符串 变成长度为m的b字符串 最小的操作次数

集合划分
1111.png

#include<bits/stdc++.h>
#include<string.h>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
const ll mod = 1e9+7;
ll n, m;
char a[maxn], b[maxn];
ll f[1010][1010];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    cin >> m;
    for(int i = 1; i <= m; i ++) cin >> b[i];

    for(int i = 0; i <= m; i ++)
    f[0][i] = i;
    for(int i = 0; i <= n; i ++)
    f[i][0] = i;

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            //这里要先判断是否增添,在判断是否不需要修改
            f[i][j] = min(f[i-1][j]+1, f[i][j-1] + 1);
            if(a[i] == b[j])
                f[i][j] = min(f[i][j], f[i-1][j-1]);
            else
                f[i][j] = min(f[i][j], f[i-1][j-1] + 1);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}



#include<bits/stdc++.h>
#include<string.h>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
const ll mod = 1e9+7;
ll n, m;
char a[maxn], b[maxn];
ll f[1010][1010];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= m; i ++) cin >> b[i];

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(a[i] == b[j])
            {
                f[i][j] = f[i-1][j-1] + 1;
            }
            else
            {
                f[i][j] = max(f[i][j-1],max(f[i-1][j], f[i-1][j-1]));
            }
        }
    }

    cout << f[n][m] << endl;
    return 0;
}



#include<bits/stdc++.h>
#include<string.h>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
const ll mod = 1e9+7;
ll n;
ll a[maxn], b[maxn];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    vector<int> ve;
    ve.push_back(a[1]);
    for(int i = 2; i <= n; i ++)
    {
        if(a[i] > ve.back())
        {
            ve.push_back(a[i]);
        }
        else
        {
            *lower_bound(ve.begin(), ve.end(), a[i]) = a[i];
        }
    }
    cout << ve.size() << endl;
    return 0;
}



题目: 最长上升子序列
要求: 有优化,虽然说是二分, 但其实更像贪心一点

思想: 用一个数字来从小到大存每个数字为结尾的最长上升序列
比如说 有 存储的序列 3 6 7 代表 以3 结尾的最长为1, 以6结尾的最长为2 以7结尾的最长为3

#include<bits/stdc++.h>
#include<string.h>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
const ll mod = 1e9+7;
ll n;
ll a[maxn], b[maxn];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    vector<int> ve;  //用来存储每个数字结尾,对应的最长子序列
    ve.push_back(a[1]);
    for(int i = 2; i <= n; i ++)
    {
        if(a[i] > ve.back())
        {
            ve.push_back(a[i]);
        }
        else
        {       // 替换掉第一个大于等于当前数字
            *lower_bound(ve.begin(), ve.end(), a[i]) = a[i];
        }
    }
    cout << ve.size() << endl;
    return 0;
}

这个思路是来自题解第一个的大佬的,tql