TIOJ 1014 . 打地鼠

終於打完地鼠了XD

一直沒有注意到 "早打一定比較好" 這性質XD

亂寫亂掃，原本估計是會T的，沒想到AC了XDD

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
int sts[1<<16][17];
int tn[16];
const int inf = 2000000000;
int nabs(int a){return max(a, -a);}
void printsts(int n){
    for(int lx = 0;lx < (1<<n);lx++){
        for(int ly = 0; ly < n;ly++)
            printf("%c", (lx&(1<<(n-ly-1))) ? '1':'0');
        printf("\t");
        for(int ly = 0;ly < n;ly++)
            if(sts[lx][ly] == inf)
                printf("inf\t");
            else
                printf("%d\t", sts[lx][ly]);
        puts("");
    }
    puts("----------------------------");
    return;
}

int main()
{
    int n; scanf("%d", &n);
    int MM = n;
    for(int lx = 0;lx < n;lx++){
        scanf("%d", tn+lx);
        MM += tn[lx];
    }
//    memset(sts, 0, sizeof(sts));
    for(int lx = 0;lx < 16;lx++)
        for(int st = 0; st < 1<<16;st++)
            sts[st][lx] = inf;
    for(int lx = 0;lx < n;lx++)
        sts[1<<lx][lx] = (lx+tn[lx])/tn[lx]*tn[lx];
    //printsts(n);
    for(int _ = 0;_ <= 16; _++){
        //printsts(n);
        for(int lx = 0;lx < n;lx++){
            for(int ly = 0;ly < 1<<n;ly++){
                if(sts[ly][lx] == inf) continue;
                for(int lz = 0;lz < n;lz++){
                    sts[ly|(1<<lz)][lz] = min(
                        sts[ly|(1<<lz)][lz],
                        (sts[ly][lx]+nabs(lz-lx)+tn[lz]-1)/tn[lz]*tn[lz]
                    );
                }
            }
        }
        //bool ok = false;
        //for(int lx = 0;lx < n and not ok;lx++)
        //    ok = sts[(1<<n)-1][lx] < inf;
        //if(ok)
        //    break;
    }
    //printsts(n);
    int mm = inf;
    for(int lx = 0;lx < n;lx++)
        mm = min(sts[(1<<n)-1][lx], mm);
    printf("%d\n", mm);
    //while(1);
    return 0;
}