牛客练习赛75 B 小D和他的魔法石

牛客练习赛75 B 小D和他的魔法石
题目连接：https://ac.nowcoder.com/acm/contest/10507/B

启用贪心的想法用完k次机会，再使用完全背包即可
贪心思路就是大的魔力配合上小的抗力，因为1e3的数据量，所以n2的做法也可以
对每一棵魔法树的魔力进行从大到小的排序，往后找最小的抗力来对这棵树的抗力进行交换，
结束上述过程后如果机会k还有剩余，那么对k的情况进行判断
如果k是偶数，那么直接忽略，因为俩颗树交换俩次等于不变

const int MAXN=1e3+10;
typedef long long ll;
#define INF 0x3f3f3f3f
ll dp[MAXN];

struct node{
    ll ai,bi;
    friend bool operator <(node a,node b){
        return a.bi>b.bi;
    }
}a[MAXN];

int main()
{
    int n,m,k,i,j;
    scanf("%d %d %d",&n,&m,&k);
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i].ai);
    }
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i].bi);
    }
    sort(a+1,a+n+1);
    i=1;
    while(k>0){
        ll minm=INF,ind=0;
        for(j=i+1;j<=n;j++){
            if(a[j].ai<minm){
                minm=a[j].ai;
                ind=j;
            }
        }
        if(minm<a[i].ai){
            a[ind].ai=a[i].ai;
            a[i].ai=minm;
            k--;
        }
        i++;
        if(i>n) break;
    }
    if(k%2){
        ll temp=a[n-1].ai;
        a[n-1].ai=a[n].ai;
        a[n].ai=temp;
    }
    for(i=1;i<=n;i++){
        for(j=a[i].ai;j<=m;j++){
            dp[j]=max(dp[j],dp[j-a[i].ai]+a[i].bi);
        }
    }
    printf("%lld\n",dp[m]);
    return 0;
}