题解 P1216 【[USACO1.5]数字三角形 Number Triangles】

· · 题解

看了洛谷日报的模拟退火算法，传送门，决定用一道简单题目练练手，具体算法的讲解文章已经非常详细。 结果错了最后3个点，因为解空间不连续，数据大的时候容易陷入局部最优解，不容易跳出来。但也是一种方法，对于理解模拟退火还是很有帮助的。 

#include <bits/stdc++.h>
#define re register
using namespace std;

int a[1010][1010];
int n,tt;
bool sx[1010];//搜索顺序，0代表选下面更大的数字，1选更小的，初始值全是0，就变成贪心，从贪心的结果出发

double ans,t; //全局最优解、温度
const double delta=0.997; //降温系数

void input() {
    scanf("%d",&n);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=i; j++)
            scanf("%d",&a[i][j]);
}
//计算和
int jisuan() {
    int tmpans=a[1][1],x=1,y=1;
    for (re int i=1; i<n; i++) {
        if (sx[i]) {
            if (a[x+1][y]<a[x+1][y+1])
                tmpans+=a[x+1][y],++x;
            else
                tmpans+=a[x+1][y+1],++x,++y;
        } else {
            if (a[x+1][y]>a[x+1][y+1])
                tmpans+=a[x+1][y],++x;
            else
                tmpans+=a[x+1][y+1],++x,++y;
        }
    }
    return tmpans;
}

inline void simulate_anneal() { //SA主过程

    t=2000; //初始温度
    while (t>1e-14) {
        srand(rand());

        int w=rand()%(n)+1; //随机更改其中一个方向

        sx[w]^=true;
        int now=jisuan();
        int Delta=now-ans;
        if (Delta>0) { //接受
            ans=now;

        } else if (exp(-Delta/t)*RAND_MAX<rand()) sx[w]^=true; //以一个概率接受
        t*=delta;

    }
}

int main() {
    srand(125897);
    srand(rand());
    srand(rand()); //玄学srand

    input();
    ans=jisuan();
    simulate_anneal();
    simulate_anneal();

    cout<<ans<<endl;
    return 0;
}