I NEED A OFFER!

时间：2011-04-23 来源：hut-tc

这道题其实质是一个01背包问题，dp[i][j]表示选择i个学校时，花费j,不能得到一份officer的概率，其状态转移方程为dp[i][j]=min(dp[i-1][j],dp[i-1][j-cost[i]]*(1-p[i]).)

刚开始时我用的是二维数组，结果MLE,然后改为一维数组，AC了......

两种情况代码如下：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cost[1010];
float dp[10010];
float p[1010];
const int inf=0x7fffffff;
float fun(float x,float y)
{
  return x>y?y:x;
}
int main( )
{
  int N,M;
  while(scanf("%d%d",&N,&M)!=EOF&&(N||M))
  {
    int i,j,k,m,n;
    float sum=1;
    for(i=1;i<=M;i++)
    scanf("%d%f",&cost[i],&p[i]);
   // for(i=0;i<=M;i++)
     for(i=0;i<=N;i++)
      dp[i]=1;
   // for(i=0;i<=M;i++)
     //dp[i][0]=1;
      for(i=1;i<=M;i++) 
       for(j=N;j>=cost[i];j--)
       {
      dp[j]=fun(dp[j],dp[j-cost[i]]*(1-p[i]));
      //printf("%d:%.2f ",j,dp[j]);
      }
     printf("%.1f%%\n",(1-dp[N])*100);
}
return 0;
}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cost[1010];
float dp[1010][10010];
float p[1010];
const int inf=0x7fffffff;
float fun(float x,float y)
{
  return x>y?y:x;
}
int main( )
{
  int N,M;
  while(scanf("%d%d",&N,&M)!=EOF&&(N||M))
  {
    int i,j,k,m,n;
    float sum=1;
    for(i=1;i<=M;i++)
    scanf("%d%f",&cost[i],&p[i]);
    for(i=0;i<=M;i++)
     for(j=0;j<=N;j++)
      dp[i][j]=1;
    for(i=0;i<=M;i++)
     dp[i][0]=1;
      for(i=1;i<=M;i++) 
       for(j=1;j<=N;j++)
        if(j>cost[i])
        {
         dp[i][j]=fun(dp[i-1][j],dp[i-1][j-cost[i]]*(1-p[i]));
        // printf("***i=%d: %.2f ",i,dp[i][j]);
         //puts(" ");
        }
        else
        {
        dp[i][j]=dp[i-1][j];
       // printf("i=%d : %.2f ",i,dp[i][j]);
       // puts(" ");
        }
     printf("%.1f%%\n",(1-dp[M][N])*100);
}
return 0;
}