red_coder's blog

By red_coder, 12 years ago, In English

Guys can anyone give me some hint on how to do this DP Problem..

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone pls give some hint

  • »
    »
    12 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Dijkstra. DP on the DAG (Direct Acyclic Graph)
    Do you understand problem?
    1) the benefit is not money.
    2) it is bad to cook the dishes two times in a row, but you can repeat some two dishes (1 3 1 3 1 3 1 ... ) and there will be profit v each time you cook this dishes.
    d[numberOfday][previousUsedDish][howManyTimesPreviosDishWasUsedInARow (range 0..3 is enough)][ourBudget] — total benefit

    • »
      »
      »
      12 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      i tried but my code is not running fine.. here is my code

      /*
      written by- Piyush Golani
      language- c++
      country- India
      College- N.I.T Jamshedpur
      */
      #include <cmath>
      #include <ctime>
      #include <iostream>
      #include <string>
      #include <vector>
      #include<cstdio>
      #include<sstream>
      #include<algorithm>
      #include<cstdlib>
      #include<cstring>
      #include<map>
      #include<cctype>
      using namespace std;
      #define pb push_back
      #define all(s) s.begin(),s.end()
      #define f(i,a,b) for(int i=a;i<b;i++)
      #define F(i,a,b) for(int i=a;i>=b;i--)
      #define PI 3.1415926535897932384626433832795
      #define INF 1000000005
      #define BIG_INF 7000000000000000000LL
      #define mp make_pair
      #define eps 1e-9
      #define LL long long
      #define si(n) scanf("%d",&n)
      #define sll(n) scanf("%lld",&n)
      #define mod 1000000007
      #define mm 55
      
      
      int K,n,m;
      int C[mm],V[mm];
      double dp[22][105][mm][4];
      map<int,double> M;
      
      double solve()// dp[a][b][c][d]= maximum benifit after 'a' days with 'b' budget when previous dish used is 'c' and it is used 'd' times in a row
      {
          f(i,1,K+1)
          {
              f(j,1,m+1)
              {
                  f(k,1,n+1)
                  {
                      f(l,1,4)
                      {
                          if(l>1)
                          {
                              dp[i][j][k][l]=dp[i-1][j-C[k]][k][l-1]+V[k]*M[l];
                          }
                          else
                          {
                              f(p,1,n+1)
                              {
                                  if(p==k) continue;
                                  f(h,1,4)
                                  {
                                      dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j-C[k]][p][h]+V[k]);
                                  }
      
                              }
                          }
                      }
      
                  }
              }
          }
          double res=0.0;
          f(i,1,n+1)
          {
              f(j,1,4)
              {
                  res=max(res,dp[K][m][i][j]);
              }
          }
          return res;
      }
      
      
      int main()
      {
          M[1]=1.0;
          M[2]=0.5;
          M[3]=0.0;
          while(1){
          si(K); si(n); si(m);
          if(K==0 && n==0 && m==0) return 0;
          memset(dp,0.0,sizeof(dp));
          f(i,0,n)
          {
              si(C[i]);
              si(V[i]);
          }
          printf("%f\n",solve());
          }
          return 0;
      }