论MC中的数学 - Project1 - Powered by Discuz!

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
// 0 water 1 veg
int dp[9][(1<<9)][1<<9];
bool checkok(int now, int upper, int upper1) {
if (upper & 1){
if ((now & 1) && (upper1 & 1) && ((upper >> 1) & 1))
return false;
}
if ((upper >> 8) & 1){
if (((now>>8) & 1) && ((upper1>>8) & 1) && ((upper >> 7) & 1))
return false;
}
for (int i = 1; i < 8; i++) {
if ((upper >> i) & 1) {
if ( ((upper >> (i - 1))&1) && ((upper >> (i + 1))&1) && ((now >> (i))&1) && ((upper1 >> (i))&1)) {
return false;
}
}
}
return true;
}
int count1(int x){
int cnt = 0;
while (x){
cnt+=x&1;
x >>= 1;
}
return cnt;
}
int main(){
for (int i = 0; i < (1<<9); i++){
dp[0][i][(1 << 9) - 1] = count1(i);
}
for (int i = 1; i < 9; i++){
for (int now = 0; now < (1<<9); now++){
for (int upper = 0; upper < (1<<9); upper++)
for (int upper1 = 0; upper1 < (1<<9); upper1++){
if (checkok(now, upper, upper1)) {
dp[i][now][upper] = max(dp[i][now][upper], dp[i - 1][upper][upper1] + count1(now));
}
}
}
}
int ans = 0;
for (int upper = 0; upper < (1<<9); upper++) {
for (int upper1 = 0; upper1 < (1<<9); upper1 ++){
if (checkok((1<<9) - 1, upper, upper1)) {
ans = max(ans, dp[8][upper][upper1]);
}
}
}
printf("%d\n", ans);
}

复制代码

function [X, Out] = MC_gurobi(A, opts)
    %% Importing options
    init;
    %% Importing Gurobi API
    addpath(opts.path);
    %% Define model
    n = size(A, 1);
    model.obj = ones(2*n, 1);
    model.A = sparse([A, -eye(n)]);
    model.sense = '<';
    model.rhs = zeros(n, 1);
    model.lb = [zeros(n,1); -ones(n,1)];
    model.rb = [ones(n,1); ones(n,1)];
    model.vtype = 'I';
    model.modelname = 'MC-minimum';
    %% Set parameters
    param.method = -1;
    param.outputflag = 0;
    %% call solver
    tt = tic;
    Res = gurobi(model, param);
    tt = toc(tt);
    %% Exporting solutions
    x = Res.x;
    X = x(1:n);
    Out.tt = tt;
    Out.flag = Res.status;
    Out.fval = Res.objval;
    Out.itr = Res.baritercount;
    %% nested function
    function init
        if ~isfield(opts, 'path'); opts.path = '/opt/gurobi701/linux64/matlab'; end;
    end
end

function [X, Out] = MC_gurobi(A, opts)


    %% Importing options


    init;


    %% Importing Gurobi API


    addpath(opts.path);


    %% Define model


    n = size(A, 1);


    model.obj = ones(2*n, 1);


    model.A = sparse([A, -eye(n)]);


    model.sense = '<';


    model.rhs = zeros(n, 1);


    model.lb = [zeros(n,1); -ones(n,1)];


    model.rb = [ones(n,1); ones(n,1)];


    model.vtype = 'I';


    model.modelname = 'MC-minimum';


    %% Set parameters


    param.method = -1;


    param.outputflag = 0;


    %% call solver


    tt = tic;


    Res = gurobi(model, param);


    tt = toc(tt);


    %% Exporting solutions


    x = Res.x;


    X = x(1:n);


    Out.tt = tt;


    Out.flag = Res.status;


    Out.fval = Res.objval;


    Out.itr = Res.baritercount;


    %% nested function


    function init


        if ~isfield(opts, 'path'); opts.path = '/opt/gurobi701/linux64/matlab'; end;


    end


end

dim = 9;
n = dim ^ 2;
A = gallery('poisson', dim);
for i = 1:n; A(i, i) = -1; end;
 
[x, Out] = MC_gurobi(A, []);
y = A * x;
X = reshape(x, 9, 9);
Y = reshape(y, 9, 9);
 
axis off;
%rectangle('Position', [1, 1, 9, 9], 'FaceColor', [0, .7, 0]);
for i=1:dim
    for j=1:dim
        pos = [i, j, 1, 1];
        if X(i, j) == 1
            rectangle('Position', pos, 'FaceColor', [0, 0, .7]);
        elseif Y(i, j) < 0
            rectangle('Position', pos, 'FaceColor', [0, .7, 0]);
        else
            rectangle('Position', pos);
        end
    end
end

dim = 9;


n = dim ^ 2;


A = gallery('poisson', dim);


for i = 1:n; A(i, i) = -1; end;


 


[x, Out] = MC_gurobi(A, []);


y = A * x;


X = reshape(x, 9, 9);


Y = reshape(y, 9, 9);


 


axis off;


%rectangle('Position', [1, 1, 9, 9], 'FaceColor', [0, .7, 0]);


for i=1:dim


    for j=1:dim


        pos = [i, j, 1, 1];


        if X(i, j) == 1


            rectangle('Position', pos, 'FaceColor', [0, 0, .7]);


        elseif Y(i, j) < 0


            rectangle('Position', pos, 'FaceColor', [0, .7, 0]);


        else


            rectangle('Position', pos);


        end


    end


end