基于空间连续块的稀疏注意力机制

#include "bits/stdc++.h"
using namespace std;

int n,m,d,b;
const double INF = 1e18;
vector<double> w1,w2;
vector<vector<double>> mat;

vector<double> handle(vector<vector<double>> block, int start, int end) {
    int col = block[0].size();
    vector<double> res(col);
    double sum;
    for(int i = 0; i < col; i++){
        sum = 0.0;
        for(int j = start; j < end; j++){
            sum = sum + block[j][i];
        }
        res[i] = sum / (end - start);
    }
    return res;
}

double dot(vector<double> vector1, vector<double> vector2) {
    double res = 0.0;
    for(int i = 0; i < vector1.size(); i++){
        res = res + vector1[i] * vector2[i];
    }
    return res;
}

vector<double> calc(vector<double> vector1, double d, int b2) {
    int sz = vector1.size();
    vector<double> res(sz);
    for(int i = 0; i < sz; i++){
        res[i] = vector1[i] * d + b2;
    }
    return res;
}

double dfs(int idx, double s1, double s2, bool f1, bool f2, vector<double> ak,int m) {
    // 已经分配结束
    if (idx == m){
        // 保证两段都有值
        if(f1 && f2){
            return fmin(s1,s2);
        }else{
            return -INF; // 返回一个极大值
        }
    }
    double op1,op2;
    // 将当前数分给s1
    op1 = dfs(idx+1,s1 + ak[idx],s2, true,f2,ak,m);
    // 分给s2
    op2 = dfs(idx+1,s1,s2 + ak[idx],f1, true,ak,m);
    return fmax(op1,op2);
}

int main(){
    // 输入
    cin >> n >> d >> b;
    mat.resize(n,vector<double>(d,0.0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < d; j++){
            cin >> mat[i][j];
        }
    }
    w1.resize(d,0.0);
    w2.resize(d,0.0);
    for(int i = 0; i < d; i++){
        cin >> w1[i];
    }
    for(int i = 0; i < d; i++){
        cin >> w2[i];
    }
    // 模拟
    double S = -INF;
    // m为块数
    m = n / b;
    if (n % b != 0) m++;
    vector<vector<double>> hk(m,vector<double>(n,0.0));
    vector<double> sk(m), zk(m), ak(m);
    vector<vector<double>> ck(m,vector<double>(n,0.0));
    vector<double> q(d,1.0);
    int b1 = 2, b2 = 1;
    // 求h1...hm
    for(int i = 1; i <= m; i++) {
        hk[i-1] = handle(mat, (i - 1) * b, min(i * b, n));
        sk[i-1] = dot(w1,hk[i-1]) + b1;
        zk[i-1] = fmax(0.0,sk[i-1]);
        ck[i-1] = calc(w2,zk[i-1],b2);
        ak[i-1] = dot(q,ck[i-1]) / sqrt(d);
    }
    // 将ak分为两段，和分别为S1，S2，最大化min(S1,S2)
    if (m == 1) S = ak[0];
    else S = fmax(S,dfs(0,0,0,false,false,ak,m));
    // 输出
    cout << round(100 * S);
    return 0;
}