头像




离线:3小时前


最近来访(8)
用户头像
F_58
用户头像
Unstoppable_Pikachu
用户头像
枕月牧星
用户头像
test886
用户头像
mmkl
用户头像
我永远喜欢结城明日奈
用户头像
Nan97
用户头像
wW



4天前

分组背包问题

思路

1.先把每组看成一个整体,把这个整体当成01背包问题来处理
2.在整体选择下每组的物体进行一个循环,选择每组的一个最优的结果

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e2+10;
int f[N],n,m;
typedef pair<int, int> PII;
vector<PII> v[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            int x,y;
            cin>>x>>y;
            v[i].push_back({x,y});
        }
    }

    for(int i=1;i<=n;i++)
    for(int k=m;k>=1;k--)
    for(int j=0;j<v[i].size();j++)//如果这两层循环的位置反了那么你做这题就相当于做一个01背包问题了!所以切记不能反
    if(k>=v[i][j].first)
    f[k]=max(f[k],f[k-v[i][j].first]+v[i][j].second);
    cout<<f[m]<<endl;
    return 0;
}




4天前

多重背包问题II(二进制优化)

思路

这个比原问题难就难在数据范围更大,如果不采用二进制优化是过不了的,我个人理解这个方法也就是对原问题的一个等价转化,转化成了一个01背包问题!
见: https://www.acwing.com/solution/content/20115/

代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=2e3+10;
int n,v,f[N];
typedef pair<int,int> PII;
vector<PII> things;
int main()
{
    cin>>n>>v;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int k=1;k<=s;k*=2)
        {
            s-=k;
            things.push_back({v*k,w*k});
        }
        if(s>0)
        things.push_back({v*s,w*s});
    }
    for(auto x:things)
    {
        for(int j=v;j>=x.first;j--)
        f[j]=max(f[j],f[j-x.first]+x.second);
    }
    cout<<f[v]<<endl;
    return 0;
}




4天前

完全背包问题

思路

这里只提一嘴状态转移方程的一个优化,优化后可以减少一个循环,降低时间复杂度
优化方法如下:
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w, .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w, f[i-1,j-2v]+2w , .....)
通过上述比较,可以得到 f[ i ][ j ] = max(f[ i - 1 ][ j ],f[ i ][ j - v ] + w)
代码里面的细节可以自己思考

不优化的代码(也能ac)

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1e3+10;
typedef pair<int, int> PII;
PII a[N];
int f[N],n,v;
int main()
{
    cin>>n>>v;
    for(int i=1;i<=n;i++)
    cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++)
    for(int j=v;j>=1;j--)
    for(int k=0;k*a[i].x<=j;k++)
    f[j]=max(f[j],f[j-k*a[i].x]+k*a[i].y);
    cout<<f[v]<<endl;
    return 0;
}

优化后的代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e3+10;
int n,v,f[N];
typedef pair<int,int> PII;
PII a[N];
int main()
{
    cin>>n>>v;
    for(int i=1;i<=n;i++)
    cin>>a[i].first>>a[i].second;

    for(int i=1;i<=n;i++)
    for(int j=a[i].first;j<=v;j++)
    f[j]=max(f[j],f[j-a[i].first]+a[i].second);

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




6天前

区间DP+环形处理

思路

把环形转化成链状即可,具体操作方法:将数组复制一倍到原数组后面形成一个长度为2n的新数组
其他思路和我之前链状的石子合并DP题解一样,不过细节上还是有些小区别

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e2+10;
int n,f1[N][N],a[N],f2[N][N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int i=1;i<=2*n;i++)
    a[i]+=a[i-1];

    for(int len=1;len<=n-1;len++)//顺带一提我这样循环遍历直接避开了i=j的情况,由于f[i][i]=0所以也不需要考虑
    for(int i=1;i+len<=2*n;i++)//循环细节点1:i+len<=2*n
    {
        int j=i+len;
        f1[i][j]=INT_MAX;
        f2[i][j]=INT_MIN;
        for(int k=0;k<len;k++)
        {
            f1[i][j]=min(f1[i][j],f1[i][i+k]+f1[i+k+1][j]+a[j]-a[i-1]);
            f2[i][j]=max(f2[i][j],f2[i][i+k]+f2[i+k+1][j]+a[j]-a[i-1]);
        }
    }
    int res_min=INT_MAX;
    int res_max=INT_MIN;
    for(int i=1;i<=n;i++)//还有这个循环选取答案,链状是直接输出f[1][n]                                   
    {
        res_min=min(res_min,f1[i][i+n-1]);
        res_max=max(res_max,f2[i][i+n-1]);
    }
    cout<<res_min<<endl;
    cout<<res_max<<endl;
    return 0;
}




6天前

难想的线性DP

思路

详情见: https://www.luogu.com.cn/problem/solution/P4059
1.状态表示:f[i][j][k],表示的是字符串A已经匹配了前i个字符,B匹配了前j个字符,k表示空格的位置的最大相似度.
空格的位置一共有四种情况:
1.A,B两字符串都不加空格
2.A后加空格,B不加
3.B后加空格,A不加
4.A,B后都加空格
第四种情况可以直接排除,因为如果都加空格的话最大相似度一定会减少.
2.状态转移:
f[i][j][0]=max(f[i-1][j-1][0],max(f[i-1][j-1][1],f[i-1][j-1][2]))+map1[t1][t2];
f[i][j][1]=max(f[i][j-1][0]-A,max(f[i][j-1][1]-B,f[i][j-1][2]-A));
f[i][j][2]=max(f[i-1][j][0]-A,max(f[i-1][j][1]-A,f[i-1][j][2]-B));

3.边界表示:
f[i][0][0]=f[i][0][2]=-inf,f[i][0][1]=-A-B(i-1);(1<=i<=la)
f[0][j][0]=f[0][j][1]=-inf,f[0][j][2]=-A-B(j-1);(1<=j<=lb)
f[0][0][0]=f[0][0][1]=f[0][0][2]=0;

这个可以根据状态转移方程推出,多思考一下

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=3e3+10;
int map1[4][4],A,B,f[N][N][3];
string change(string s)
{
    for(int i=0;i<s.size();i++)
    if(s[i]=='A')
    s[i]='0';
    else if(s[i]=='T')
    s[i]='1';
    else if(s[i]=='G')
    s[i]='2';
    else if(s[i]=='C')
    s[i]='3';
    return " "+s;
}
int main()
{
    string a,b;
    cin>>a>>b;
    int la=a.size();
    int lb=b.size();
    a=change(a);
    b=change(b);
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++)
    cin>>map1[i][j];
    cin>>A>>B;
    for(int i=1;i<=la;i++)
    {
        f[i][0][0]=-inf;
        f[i][0][1]=-A-B*(i-1);
        f[i][0][2]=-inf;
    }
    for(int i=1;i<=lb;i++)
    {
        f[0][i][0]=-inf;
        f[0][i][1]=-inf;
        f[0][i][2]=-A-B*(i-1);
    }
    for(int i=1;i<=la;i++)
    for(int j=1;j<=lb;j++)
    {
        int t1=a[i]-'0',t2=b[j]-'0';
        f[i][j][0]=max(f[i-1][j-1][0],max(f[i-1][j-1][1],f[i-1][j-1][2]))+map1[t1][t2];
        f[i][j][1]=max(f[i][j-1][0]-A,max(f[i][j-1][1]-B,f[i][j-1][2]-A));
        f[i][j][2]=max(f[i-1][j][0]-A,max(f[i-1][j][1]-A,f[i-1][j][2]-B));
    }
    cout<<max(f[la][lb][0],max(f[la][lb][1],f[la][lb][2]))<<endl;
    return 0;
}




7天前

简单DP

思路

1.状态表示:f[N][2],其中f[i][0]表示到达第i行的左端点所需的最小步数,f[i][1]表示到达第i行的右端点所需的最小步数
2.状态转移:
f[i][0]=min(f[i-1][0]+dis(l[i-1]-l[i]),f[i-1][1]+dis(r[i-1],l[i]))+r[i]-l[i]+1
f[i][1]=min(f[i-1][0]+dis(l[i-1]-r[i]),f[i-1][1]+dis(r[i-1],r[i]))+r[i]-l[i]+1
3.边界情况
f[1][1]=r[1]-1
f[1][0]=(r[1]-1)+(r[1]-l[1])

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=2e4+10;
int n,f[N][2];
int l[N],r[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int l1,r1;
        cin>>l1>>r1;
        l[i]=l1;
        r[i]=r1;
    }
    f[1][1]=r[1]-1;
    f[1][0]=(r[1]-l[1])+(r[1]-1);
    for(int i=2;i<=n;i++)
    {
        f[i][0]=min(f[i-1][0]+abs(l[i-1]-r[i]),f[i-1][1]+abs(r[i-1]-r[i]))+1+r[i]-l[i];
        f[i][1]=min(f[i-1][0]+abs(l[i-1]-l[i]),f[i-1][1]+abs(r[i-1]-l[i]))+1+r[i]-l[i];
    }
    cout<<min(f[n][0]+n-l[n],f[n][1]+n-r[n])<<endl;
    return 0;
}




8天前

思维+二分+暴力

思路

题目中描述的 i<j 这一条可以忽略,这题就是想让求 i!=j且l<=a[i]+a[j]<=r 这样的 (i,j) 一共有多少对.利用二分查找大于等于l-a[j]和小于等于r-a[j]在a数组的两个位置,并计算r-l+1即可.
我感觉我这题是误打误撞混对的

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N=2e5+10;
typedef long long ll;
int t,n,l,r,a[N];
int main()
{
    cin>>t;
    while(t--)
    {
        memset(a,0,sizeof a);
        cin>>n>>l>>r;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        sort(a+1,a+n+1);
        long long res=0;//这里不定义long long这题过不了
        for(int i=1;i<n;i++)
        {
            int l1,r1;
            l1=lower_bound(a,a+n,l-a[i])-a;
            int left=1,right=n,x=r-a[i];
            while(left<right)
            {
                int mid=(left+right+1)>>1;
                if(a[mid]<=x) left=mid;
                else
                right=mid-1;
            }
            r1=left;
            if(a[r1]+a[i]>=l&&a[i]+a[i+1]<=r)
            {
                if(l1<=i&&r1>i)
                res+=r1-i;
                else if(l1>i&&r1>i)
                res+=r1-l1+1;
                //去重操作,也可以每轮直接加l-r+1最后除2
            }
        }
        cout<<res<<endl;
    }
    return 0;
}




8天前

模拟+思维

思路

假设第一个选手为A,第二个选手为B
1.A=1,B=1或者A=1,B=2或者A=2,B=1均使得ans[A][B]=’=’,ans[B][A]=’=’.
2.A=2,B=2使得ans[A][B]=’+’,ans[B][A]=’-‘.
当时打的时候被折磨了半天,其实思路都是对的,就是因为PII a[n],放到局部变量里没有放全局变量导致在测评时候a[n]的初始值不是我想要的所以就一直WA,但是在acwing上的测评是对的就离谱,以后注意!!!

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 60;
int t, n;
string s;
char ans[N][N];
PII a[N];
int main()
{

    cin >> t;
    while (t--)
    {
        memset(ans, -1, sizeof ans);
        cin >> n >> s;
        for (int i = 1; i <= n; i++)
            ans[i][i] = 'X';
        for(int i=1;i<=n;i++)
        a[i].second=0;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '1')
                a[i + 1].first = 1;
            else
                a[i + 1].first = 2;
        }

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if (i != j)
                {
                    if ((a[i].first == 1 && (a[j].first == 1 || a[j].first == 2)) || (a[i].first == 2 && a[j].first == 1))
                    {
                        if (ans[i][j] == -1 && ans[j][i] == -1)
                        {
                            ans[i][j] = '=';
                            ans[j][i] = '=';
                        }
                    }
                    else if (a[i].first == 2 && a[j].first == 2 && a[i].second == 0)
                    {
                        if (ans[i][j] == -1 && ans[j][i] == -1)
                        {
                            a[i].second = 1;
                            ans[i][j] = '+';
                            ans[j][i] = '-';
                        }
                    }
                }
            }        
        int flag = 0;
        for (int i = 1; i <= n; i++)
            if (a[i].first == 2 && a[i].second == 0)
                flag = 1;
        if (!flag)
        {
            cout << "YES" << endl;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (ans[i][j] == -1)
                    ans[i][j] = '=';
                    cout << ans[i][j];
                }
                cout << endl;
            }
        }
        else
            cout << "NO" << endl;
    }
    return 0;
}




8天前

思维+暴力

思路

1.i+j<=2*n
2.由于a[i] * a[j]=i+j 所以a[i] * a[j]<=2*n
3.由于第二点可以计算出这样的(i,j)对数最多有nlogn对,计算方法便是假设a[i]=1,2,3…n然后计算a[j]的个数,详情可见:
https://codeforces.com/blog/entry/92199

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10;
int t, n;
PII a[N];
int main()
{

    cin >> t;
    while (t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            a[i]={x,i};
        }
        sort(a+1,a+n+1);
        int res=0;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(a[i].first*a[j].first>2*n)
        break;
        else if(a[i].second<a[j].second&&a[i].first*a[j].first==a[i].second+a[j].second)
        res++;
        cout<<res<<endl;
    }
    return 0;
}




13天前

简单DP

思路

把输入的2变成1,输入的1变成-1,并求出前缀和(用前缀和是为了防止超时)
1.状态表示:f[i]表示到以i结尾的学生为止所需要的最少机房数
2.状态转移:0<=j<i,如果abs(s[i]-s[j])<=m||abs(s[i]-s[j])<=i-j,f[i]=min(f[i],f[j]+1),也就是如果这一段的前缀和的绝对值小于等于m,或者这一段全是1或-1可以发生该状态转移
3.边界情况:f[1]=1,当只有一个同学时至少有一个机房

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2510;
int n,m,f[N],s[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(x==2)
        s[i]+=s[i-1]+1;
        else if(x==1)
        s[i]+=s[i-1]-1;
    }
    memset(f,0x3f3f,sizeof f);
    f[0]=0;
    f[1]=1;
    for(int i=1;i<=n;i++)
    for(int j=0;j<i;j++)
    {
        if(abs(s[i]-s[j])<=m||abs(s[i]-s[j])==i-j)
        f[i]=min(f[i],f[j]+1);
    }
    cout<<f[n]<<endl;
    return 0;
}