POJ 1973
这道题以前做过的。今儿重做一次。由于每个程序员要么做A,要么做B，可以联想到0/1背包（谢谢N巨）。这样，可以设状态
dp[i][j]为i个程序员做j个A项目同时，最多可做多少个B项目。枚举最后一个程序员做多少个A项目进行转移（0/1）。
dp[i][j]=max{dp[i-1][k]+(time-(j-k)*a[i])/b[i]}。于是，二分时间time进行判定即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[110][110];
int a[110],b[110];
int n,m;
bool slove(int time){
memset(dp,-1,sizeof(dp));
for(int i=0;i<=m;i++){
if(time-i*a[1]<0) continue;
dp[1][i]=(time-i*a[1])/b[1];
}
for(int i=2;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=j;k++){
if(dp[i-1][k]<0||time-(j-k)*a[i]<0) continue;
dp[i][j]=max(dp[i][j],dp[i-1][k]+(time-(j-k)*a[i])/b[i]);
}
}
}
//bool flag=false;
for(int i=0;i<=n;i++){
if(dp[i][m]>=m) return true;
}
return false;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int l=0,r=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
r+=(a[i]*m+b[i]*m);
}
int ans=100000000;
while(l<=r){
int mid=(l+r)>>1;
if(slove(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}
POJ 1180
开始时设了二维的数组。一看范围，就知道不行了。。
可以很容易就看出是DP了。可以倒过来设状态dp[i]表示加入i任务，从i任务到n任务完成所需要的时间。
dp[i]=min{dp[j]+（s+tsum[i]-tsum[j]）*fsum[i]}//i之后的第一个分组是从j开始，枚举。
这样还不足够。可以用斜率来优化。假设j<p。如果对于决策i,j更优于p，则有dp[j]+(s+tsum[i]-tsum[j])*fsum[i]<dp[p]+(s+tsum[i]-tsum[j])*fsum[i]。化简有
dp[j]-dp[p]<(tsum[j]-tsum[p])*fsum[i]。可以看到是斜率k=g[j,p]=(dp[j]-dp[p])/(tsum[j]-tsum[p])<fsum[i]，j优于p。
对于k<j<p。如果有g[k,j]<g[j,p]。则j必定是可以不要的。因为当g[k,j]<s时，明显k优于j。否则g[k,j]>s，有s<g[k,j]<g[j,p]。说明，k不优于j,j不优于p。
于是，j是可以不要的。
斜率减少。因而可以去掉j。在这里，我们要维护的是斜率的下凸，如：g[k,j]>g[j,p]。这样，对于j点，如果j点可选，则其前面的点均可以不需要了。因为斜率是下凸，会直到某个斜率大于fsum[i]，才会选到最优。
用一个单调队列维护即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
#define LL __int64
using namespace std;
int t[10010],f[10010];
LL ts[10010],fs[10010];
int que[10010],head,tail;
LL dp[10010];
int main(){
int n,s;
while(scanf("%d",&n)!=EOF){
head=tail=0;
scanf("%d",&s);
for(int i=1;i<=n;i++){
scanf("%d%d",&t[i],&f[i]);
}
dp[n+1]=0; ts[n+1]=fs[n+1]=0;
for(int i=n;i>=1;i--){
ts[i]=(ts[i+1]+t[i]);
fs[i]=(fs[i+1]+f[i]);
}
head=tail=0;
dp[n+1]=0;
que[tail++]=n+1;
dp[n]=(s+ts[n])*fs[n];
que[tail++]=n;
for(int i=n-1;i>=1;i--){
while(head<tail-1&&dp[que[head+1]]-dp[que[head]]<=(ts[que[head+1]]-ts[que[head]])*fs[i])
head++;
dp[i]=dp[que[head]]+(s+ts[i]-ts[que[head]])*fs[i];
while(head+1<tail&&(dp[i]-dp[que[tail-1]])*(ts[que[tail-1]]-ts[que[tail-2]])<=(dp[que[tail-1]]-dp[que[tail-2]])*(ts[i]-ts[que[tail-1]]))
tail--;
que[tail++]=i;
}
printf("%I64d\n",dp[1]);
}
return 0;
}