推 JIWP: 好了啦，還不是別人教你的 12/29 22:13
→ oin1104: 我自己想到的 12/29 22:14
→ oin1104: 雖然有提示 可是我還是我想到的 12/29 22:14
→ oin1104: 不管 我很棒 12/29 22:14
推 Che31128: 你很棒 12/29 22:15
推 JIWP: = = 12/29 22:15
題目：
你有n個工作 跟d天
每天至少要做一個工作 沒有上限 加班到死
要照順序做
每天的工作難度是當天難度最大的工作的難度
問你怎麼安排行程可以讓你d天工作難度加起來最小
解法：
https://i.imgur.com/0jbL4k2.jpg
dpdpdpdpdpdpdpdpdpdp
第一天工作到哪裡 難度會多大
第二天工作到哪裡 難度加上第一天的難度會多大
第三天...
然後一直加到最後一天
的最後一格工作
就可以了
我好棒
int minDifficulty(int* jobDifficulty, int jobDifficultySize, int d)
{
int ans = 0;
int n = jobDifficultySize;
int map[d][n];
memset(map , 0 , sizeof(map));
if(n < d)
{
return -1;
}
if(n == d)
{
int haha = 0;
for(int i = 0 ; i < n ; i ++)
{
haha+=jobDifficulty[i];
}
return haha;
}
int find(int ln , int fn)
{
int maxii = 0 ;
for(int ii = ln ; ii <= fn ; ii++)
{
if(jobDifficulty[ii] > maxii)
{
maxii = jobDifficulty[ii];
}
}
return maxii;
}
int f = 0;
int l = 0;
int dnow = 1;
int fk = 0;
int max = 0;
for(int i = 0 ; i < d ; i++)
{
int minf = 0;
int min = 99999999;
for(int k = i ; k <= (n -d +i) ; k++ )
{
min = 99999999;
if(i == 0)
{
map[i][k] = find(i,k);
}
else if(i>0)
{
for(int j = i-1 ; j < k ; j ++)
{
if(map[i-1][j] + find(j+1,k) < min)
{
min = map[i-1][j] + find(j+1,k);
}
}
map[i][k] = min;
}
}
}
return map[d-1][n-1];
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.57.64 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1703859147.A.2D8.html