题目
展开 题目描述 魔兽争霸3中，战略资源的采集通过使用农民、苦工、小精灵以及寺僧来进行。
在魔兽争霸4的开发中，玻璃渣觉得这种模式太过单一，于是他们想添加更多的单位来使采集的模式更加丰富。
在新的模式中，玩家可以建造更多种类的“苦工”，不同的“苦工”的工作效率不同，同时，建造不同的“苦工”所需要的资源也是不一样的。
玻璃渣出品的游戏以追求平衡著称，所以为了测试这种新的模式的平衡性，他们设计了一套检测的方法：在各种族的起始资源相同时，测量达到某一资源数量的时间，如果相同则可以认为设计是平衡的。
他们将数据给你，希望你能测试出设计是否平衡。
输入格式 第一行三个数，N, M, T, 表示苦工的种类、开始时拥有的资源数量以及需要达到的资源的数量。
接下来N行，每行2个数A, B, 表示生产这种苦工所需要的资源，以及这个苦工的效率，效率即为单位时间内产生的资源的数量。
输出格式 一个数字，表示资源数量达到T时的最少时间。
注意：与魔兽争霸3不同，魔兽争霸4中，生产苦工不需要时间。并且资源的采集并不连续，亦即如果一个苦工的效率为2，他会在时间为1的时候收获2点资源，而并不会在时间为0.5的时候收获1点资源。
输入输出样例 输入 #1复制 1 1 8 1 1 输出 #1复制 4 输入 #2复制 2 1 8 1 1 2 8 输出 #2复制 3 说明/提示 对于30%的数据，N<=10, M, T <= 300
对于100%的数据，N<=100，M, T <= 1000, A, B <= 2^31
数据保证有解。
思路
双dp 先预处理一个完全背包f，表示用i块钱买到的最大效率 然后设dp[i][j]为前i秒，还剩j块钱，最大的效率 转移显然
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std
;
const int N
=1077;
ll n
,m
,T
,a
[N
],b
[N
],dp
[N
][N
],f
[N
];
int main()
{
scanf("%d%d%d",&n
,&m
,&T
);
if(m
>=T
)
{
printf("0"); return 0;
}
for(int i
=1; i
<=n
; i
++)
{
scanf("%lld%lld",&a
[i
],&b
[i
]);
if(a
[i
]==0&&b
[i
]>0)
{
printf("0"); return 0;
}
else if(a
[i
]==0&&b
[i
]==0) i
--,n
--;
}
for(int i
=0; i
<=T
; i
++) for(int j
=1; j
<=T
; j
++) dp
[i
][j
]=-1;
for(int i
=1; i
<=n
; i
++) for(int j
=a
[i
]; j
<=T
; j
++) f
[j
]=max(f
[j
],f
[j
-a
[i
]]+b
[i
]);
dp
[0][m
]=0;
for(int i
=0; i
<=1000; i
++) if(dp
[i
][T
]!=-1)
{
printf("%d\n",i
);
return 0;
}
else for(int j
=1; j
<=T
; j
++) if(dp
[i
][j
]!=-1)
{
for(int k
=1; k
<=j
; k
++)
{
if(f
[k
]==0) continue;
ll w
=(j
-k
)+f
[k
]+dp
[i
][j
];
if(w
>=T
)
{
printf("%d\n",i
+1); return 0;
}
dp
[i
+1][w
]=max(dp
[i
+1][w
],dp
[i
][j
]+f
[k
]);
}
}
}
