奇怪的dp
思路清奇 dp[i][j]表示当前做完了i个任务,1机器花了j秒,2机器花费的最少时间,然后转移就行了。
#include<bits/stdc++.h>
using namespace std;
const int N = ;
struct data {
int a, b, c;
} a[N];
int n, ans = 0x3f3f3f3f, pre;
int dp[][N * ];
int main()
{
scanf("%d", &n);
for(int i = ; i <= n; ++i)
{
scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c);
if(a[i].a == ) a[i].a = 0x3f3f3f3f;
if(a[i].b == ) a[i].b = 0x3f3f3f3f;
if(a[i].c == ) a[i].c = 0x3f3f3f3f;
}
for(int i = ; i <= n; ++i)
{
pre ^= ;
memset(dp[pre], 0x3f3f, sizeof(dp[pre]));
for(int j = ; j <= ; ++j)
{
if(j >= a[i].a) dp[pre][j] = dp[pre ^ ][j - a[i].a];
dp[pre][j] = min(dp[pre][j], dp[pre ^ ][j] + a[i].b);
if(j >= a[i].c) dp[pre][j] = min(dp[pre][j], dp[pre ^ ][j - a[i].c] + a[i].c);
}
}
for(int i = ; i <= ; ++i) ans = min(ans, max(i, dp[pre][i]));
cout << ans;
return ;
}