Luogu 最大收益

题解

吐槽

模拟退火
崩溃

解

正解是DP
Dp方程明显

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int maxn=3001;
struct proj {
    int w,r;
} a[maxn];
bool cmp(const proj &a,const proj &b) {
    return a.r>b.r;
}
int f[maxn][maxn];
int n,ans;
void solve() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i].w>>a[i].r;
    sort(a+1,a+1+n,cmp);
    f[1][1]=a[1].w;
    for(int i=1; i<=n; i++) for(int j=1; j<=i; j++)
            f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i].w-a[i].r*(j-1));
    for(int i=1; i<=n; i++) ans=max(f[n][i],ans);
    cout<<ans;
}
int main() {
    solve();
    return 0;
}

那个T到飞起的模拟退火
只好把 $T$ 改的小一点，那就 WA 了
这份代码50
好像只有暴力分

#include <bits/stdc++.h>
const int N = 3010 << 2;
#define DB double
const DB Delta = 0.98;
const DB eps = 1e-10;
const DB Delta2 = 0.88;
const DB eps2 = 1e-5;
int W[N], R[N];
int n;
bool Use[N];
int Beuse[N], Sum[N];
#define gc getchar()
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
inline int Work_2() {
    DB Now_temp = 1000;
    int js(0), cut(0);
    for(int i = 1; i <= n; ++ i) Sum[i] = 0;
    for(int i = 1; i <= n; ++ i) if(Use[i]) Beuse[++ js] = i;
    if(js == 1) return W[Beuse[1]];
    for(int i = 1; i <= js; ++ i) Sum[i] = Sum[i - 1] + W[Beuse[i]], cut += (js - i) * R[Beuse[i]];
    int Ans = Sum[js] - cut;
    while(Now_temp > eps2) {
        int R1 = rand() % js + 1, R2 = rand() % js + 1;
        while(R2 == R1) R2 = rand() % js + 1;
        if(R1 > R2) std:: swap(R1, R2);
        int delta = (js - R1) * (R[Beuse[R1]] - R[Beuse[R2]]) + (js - R2) * (R[Beuse[R2]] - R[Beuse[R1]]);
        if(delta > 0 || (exp((DB)-delta / Now_temp) * RAND_MAX < rand())) {
            std:: swap(Beuse[R1], Beuse[R2]);
            Ans += delta;
        }
        Now_temp *= Delta2;
    }
    return Ans;
}
int tot;
inline int Work_1() {
    DB Now_temp = 1000;
    tot = 0;
    for(int i = 1; i <= n; ++ i) Use[i] = 0;
    Use[rand() % n + 1] = 1;
    for(int i = 1; i <= n; ++ i) {
        if(!Use[i]) Use[i] = rand() % 2;
        if(Use[i])  tot ++;
    }
    int Ans = Work_2();
    while(Now_temp > eps) {
        int R1 = rand() % n + 1;
        if(Use[R1]) tot --;
        else tot ++;
        Use[R1] ^= 1;
        if(!tot) {Use[R1] ^= 1; Now_temp *= Delta; tot ++; continue ;}
        int NxtAns = Work_2();
        if(NxtAns > Ans || (exp((DB)(Ans - NxtAns) / Now_temp) * RAND_MAX < rand())) Ans = NxtAns;
        else {Use[R1] ^= 1; if(Use[R1]) tot ++; else tot --;}
        Now_temp *= Delta;
    }
    return Ans;
}
int main() {
    srand(time(0) + 20001206);
    n = read();
    for(int i = 1; i <= n; ++ i) W[i] = read(), R[i] = read();
    int T = 30;
    int Answer = 0;
    for(; T; T --) 
        Answer = std:: max(Answer, Work_1());
    std:: cout << Answer;
    return 0;
}