呵呵，剛好看到你的回復

這里沒有代碼格式
自己復制ALT + F8一下


#include<stdio.h>
#include<string>
#define Min(a,b) a>b?b:a
struct DP{
int score;
int next;
int time;
}dp[32768];
struct Homework{
int deadlion,time;
char name[101];
}hw[15];
char ans[15][101];
int n;

void dfs(int k)
{
int i,min,cnt,time,d=k,id,score,next,t;
char ch[16];

memset(ch,'0',sizeof(ch));
i = 14;
d = k;
cnt = 0;
ch[15] = 0;
while(d)
{
if(d&1)
{
cnt += d&1;
ch[i] = (d&1) + '0';
id = i;//如果只有一個1，id可以記錄下1的位子
}
i --;
d >>= 1;
}//轉化成二進制

if(cnt == 1)//最底下的情況,只完成了一種作業
{
id = 14 - id;
if(hw[id].deadlion >= hw[id].time)
dp[k].score = 0;
else
dp[k].score = hw[id].time - hw[id].deadlion;
dp[k].time = hw[id].time;
dp[k].next = id;
return ;
}

min = 0x7FFFFFFF;
for(i=0;i<15;i++)
{
if(ch[i]=='1')
{
id = 14 - i;
int kk = k - (1<<id);
if(dp[kk].time == -1)
dfs(kk);
time = dp[kk].time + hw[id].time;
score = dp[kk].score;
if(hw[id].deadlion < time)
score += (time-hw[id].deadlion);
if(score < min || score == min && strcmp(hw[id].name,hw[next].name)<0)
{
if(score<min)
next = id;
min = score;
t = time;
}
}
}
dp[k].score = min;
dp[k].next = next;
dp[k].time = t;
}


int main()
{
int T,i,k;
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
k = (1<<n)-1;//一共有這么多可能
for(i=0;i<=k;i++)
dp[i].time = -1;
for(i=0;i<n;i++)
scanf("%s%d%d",hw[i].name,&hw[i].deadlion,&hw[i].time);
dfs(k);
printf("%d\n",dp[k].score);
//輸出名字
for(i=0;i<n;i++)
{
strcpy(ans[i],hw[ dp[k].next ].name);
k = k - (1<<(dp[k].next));
}
for(i=n-1;i>=0;i--)
puts(ans[i]);
}
return 0;
}

@hhanger
哦，“映射二叉堆”原來已經有名字了的，哎呀，我孤陋寡聞了。。

呵呵，我習慣把一些數組名都取做hh的，哈哈~~

為什么。。。n是偶數的時候要除以二啊？

學習

加下我QQ吧，主頁上有477627586
估價函數不是一個準確的函數
這里設計的是每個數字離終點的距離，所以是2不是1

這個有一定概率性的
不過出現這樣的幾率非常小

也可以隨機出數據
for(int i = 0; i < n; i ++)
ku[i] = rand()%10000;

然后用數組ku作為一維數組去進行降維

@wswyb001
這個是n^4的算法
浙大模板n^3的，現在用那個。。。

@Apple
如何？
我usaco上是0.3s

@bt
這道題目雖然我解題報告寫出來了
但是我的代碼寫的很挫的。。
當時通過調試在處理好狠多小細節才過的。。
所以就不獻丑了。。再想想，處理好細節很簡單的

@ouye


num[1] = 10;
num[2] = 98
num[i] = num[i-1]*10 - num[i-2];

然后num[i] - 1就是所求的答案

@matrix


因為上下只相差一位
所以可以用
“

”


只算出第一行，然后接下來的根據移位得到

。。。
算了，這里格式不好，我貼到上邊去

@hhanger
哇。。。hh駕臨寒舍。蓬蓽生輝阿~~哈哈

好的

@future


A = [1 1 0 0]
[0 3 2 7]
[0 1 0 0]
[0 0 1 0]

B = [Sn]
[Fn-1]
[Fn-2]
[Fn-3]

大大您教我的 阿

本來整理自己看的
幾何知識一點都不會
。。。唉
被大牛們嘲笑了

@AekdyCoin


您都0.5s了。。。

@fdar


呵呵，好的

stl還要模板
直接調用函數不就行了。。。那個太懶了
堅決不寫
做個純C寫手

@fdar
呵呵
這個模板還可以優化的。。

@斌whb

數學很好玩

zero

@Apple

你又想加這么多錢

@混沌的云


zro

@AekdyCoin
恩，那個效率高很多吧

這個字典樹效率有些高有些低阿。。。
唉。。。。
還二分好一點