题目描述

jo味十足的代码

样例

4 5
1 2
2 4
3 4
4 6

思路

使用替身过题，没想到吧yxc，standpower！（doge）
使用The World来消减时间复杂度，wryyyyyyyyyyyyyyy!（doge）
使用忧郁蓝调来模仿y总写题（doge）

参考文献

无

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int theworld,killerqueen;
int winwinwin[N][N];
int wryyyyy[N],Joestar[N];
int main()
{
    cin>>theworld>>killerqueen;
    for(int dio=1;dio<=theworld;dio++)
    cin>>Joestar[dio]>>wryyyyy[dio];
    for(int i=theworld;i>=1;i--)
    for(int j=0;j<=killerqueen;j++)
    {
        winwinwin[i][j]=winwinwin[i+1][j];
        if(j>=Joestar[i])
        winwinwin[i][j]=max(winwinwin[i][j],winwinwin[i+1][j-Joestar[i]]+wryyyyy[i]);
    }
    int boki=killerqueen;
    for(int jojo=1;jojo<=theworld;jojo++)
    {
        if(boki>=Joestar[jojo]&&winwinwin[jojo][boki]==winwinwin[jojo+1][boki-Joestar[jojo]]+wryyyyy[jojo])
        {
            cout<<jojo<<" ";
            boki=boki-Joestar[jojo];
        }
    }
    return 0;
}