呵呵，刚好看到你的回复

这里没有代码格式
自己复制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
恩，那个效率高很多吧

这个字典树效率有些高有些低阿。。。
唉。。。。
还二分好一点