题目链接 完全背包

为什么这样写是错的

错误的代码：

#pragma GCC optimize(3)
#include <iostream>
#include <algorithm>

using namespace std;

#define int long long
#define endl "\n"

const int N=1010;

int v[N],w[N];
int dp[N][N];

void solve()
{
    int n,m;
    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=v[i];j<=m;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
        }    
    cout<<dp[n][m]<<endl;

    return ;
}

signed main()
{
    std::ios::sync_with_stdio(false);std::cin.tie(0);

    solve();

    return 0;
}

只错了最后一个数据

正确的代码

#pragma GCC optimize(3)
#include <iostream>
#include <algorithm>

using namespace std;

#define int long long
#define endl "\n"

const int N=1010;

int v[N],w[N];
int dp[N];

void solve()
{
    int n,m;
    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=v[i];j<=m;j++)
        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }    
    cout<<dp[m]<<endl;

    return ;
}

signed main()
{
    std::ios::sync_with_stdio(false);std::cin.tie(0);

    solve();

    return 0;
}

#pragma GCC optimize(3)
#include <iostream>

using namespace std;

#define endl "\n"
#define int long long 

const int MAX=1010;

int dp[MAX][MAX];

void solve()
{
    char a[MAX],b[MAX];
    int n,m;
    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++)
        {
            //状态转移方程
            //1. a[i]==b[j] dp[i][j]=max{dp[i-1][j],dp[i][j-1],dp[i][j]+1}
            //2. a[i]!=b[j] dp[i][j]=max{dp[i-1][j],dp[i][j-1]}
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j])  dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
        }

    cout<<dp[n][m]<<endl;

    return ;
}

signed main()
{
    std::ios::sync_with_stdio(false);std::cin.tie(0);
    solve();
    return 0;
}

堆优化dijkstra

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N=200010;

int n,m,x,y;
int dist[N];
bool st[N];
int h[N],e[N],w[N],ne[N],idx;

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void dijkstra(int x,int y)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[x]=0;
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,x});

    while(heap.size())
    {
        PII t=heap.top();
        heap.pop();
        int ver=t.second;    

        if(st[ver]) continue;
        st[ver]=true;

        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[ver]+w[i])
            {
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
    }

    if(dist[y]==0x3f3f3f3f)  puts("-1");
    else    printf("%d\n",dist[y]);    
}

signed main()
{
    std::ios::sync_with_stdio(false);std::cin.tie(0);
    memset(h,-1,sizeof h);
    cin>>n>>m>>x>>y;

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    dijkstra(x,y);

    return 0;
}

#include <iostream>
#include <queue>

using namespace std;

const int N=110;

int a[N];

int main()
{
    std::ios::sync_with_stdio(false);std::cin.tie(0);

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)   cin>>a[i];
    queue<int> q,ans;
    for(int i=1;i<=n;i++)   q.push(i);

    for(int i=1;i<=m;i++)
    {
        int k=a[i]%q.size()+1;
        for(int j=1;j<k;j++)
        {
            q.push(q.front());
            q.pop();
        }
        ans.push(q.front());
        q.pop();
    }

    while(ans.size()) 
    {
        cout<<ans.front()<<" ";
        ans.pop();
    }

    return 0;
}

#include <iostream>
#include <queue>

using namespace std;

const int N=110;

int a[N];

int main()
{
    std::ios::sync_with_stdio(false);std::cin.tie(0);

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)   cin>>a[i];
    queue<int> q,ans;
    for(int i=1;i<=n;i++)   q.push(i);
    int j=1;
    for(int i=1;i<=m;i++)
    {
        int k=a[i]%q.size()+1;
        while(j<k)
        {
            int t=q.front();
            q.pop();
            q.push(t);
            j++;
        }
        int t=q.front();
        q.pop();
        ans.push(t);
        j=1;
    }

    while(ans.size()) 
    {
        cout<<ans.front()<<" ";
        ans.pop();
    }


    return 0;
}

#pragma GCC optimize(3)
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define endl "\n"
#define int long long

typedef pair<int,int> PII;

const int N=500010,M=1000010;

int a[N],cnt[M];

signed main()
{
    std::ios::sync_with_stdio(false);std::cin.tie(0);
    int n,k;
    cin>>n>>k;
    rep(i,n)    cin>>a[i];

    int res=-1,l=-1,r=-1,tmp=0;

    int i,j;
    for(i=0,j=0;i<=j&&j<n;j++)
    {
        if(!cnt[a[j]])  tmp++;
        cnt[a[j]]++;

        if(tmp>k)
        {
            if(j-i>res)
            {
                l=i;
                r=j-1;
                res=j-i;
            }
            while(tmp>k)
            {
                cnt[a[i]]--;
                if(!cnt[a[i]])  
                {
                    tmp--;
                    i++; 
                    break;
                }
                i++;
            }
        }
    }
    if(tmp<=k)
    {
        if(j-i>res)
        {
            res=j-i;
            r=j-1;
            l=i;
        }
    }

    //cout<<res<<endl;
    cout<<l+1<<" "<<r+1<<endl;

    return 0;
}

#include <iostream>

using namespace std;

int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    string s;
    cin>>s;

    int res=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='1')   res+=a;
        if(s[i]=='2')   res+=b;
        if(s[i]=='3')   res+=c;
        if(s[i]=='4')   res+=d;
    }

    cout<<res<<endl;

    return 0;
}

#pragma GCC optimize(3)
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long

int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(f=='-')  f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

const int N=1000010;

int primes[N],cnt;
bool st[N],isP[N];

void get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])  primes[cnt++]=i,isP[i]=true;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)  break;
        }
    }
}

signed main()
{
    std::ios::sync_with_stdio(false);std::cin.tie(0);
    get_primes(N);
    while(true)
    {
        int x=read();
        if(!x)  break;
        for(int i=0;i<cnt;i++)
        {
            int a=primes[i],b=x-a;
            if(isP[b])    
            {
                printf("%lld = %lld + %lld\n",x,a,b);
                break;
            }
        }

    }

    return 0;
}

#include <iostream>

using namespace std;

#define int long long

signed main()
{
    int a,b,n;
    cin>>a>>b>>n;
    int week=a*5+b*2;
    int w=n/week,left=n-week*w;
    if(left)
    {
        int t,res=0;
        for(int i=1;i<=n;i++)
        {
            if(i<=5)    res+=a;    
            else    res+=b;
            if(res>=left)
            {
                cout<<w*7+i<<endl;
                break;
            }
        }
    }
    else
    {
        cout<<w*7<<endl;
    }

    return 0;
}

#include <iostream>

using namespace std;

#define endl "\n"

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int res=max(2*(i-1),2*(n-i));
        cout<<res<<endl;
    }

    return 0;
}