|
|
Changed < to <= when comparing dp values, and got AC I got AC by finding the solution(s) with the maximum sized grant that Warmtown can receive if both towns request grants optimally. If there are several solutions with the same grant, pick the one with the smallest grant for Freezetown (not sure if this latter sorting key is required but it worked for me). If you have WA4 try test 3 2 1 asnwer: 2 1 Edited by author 18.09.2013 18:27 my solution get wrong answer ? can anyone give me sample test cases ? or detect my error in my algorithm ? // my code //Bismillahir Rahmanir Rahim Thanks Allah 4 everything #include <stdio.h> #include <stdlib.h> #include <memory.h> #include <map> #include <queue> #include <string.h> #include <iostream> #include <algorithm> using namespace std; int dp(int a ,int opt,int k) ; int max(int m1,int m2) ; using namespace std; int save[10002][102] ; int call[10002][102] ;
int k1; int max_b=0; int n,m,k2; int main() {
while((scanf("%d%d%d",&n,&m,&k2))==3) { memset(save,0,sizeof(save)); memset(call,0,sizeof(call)); k1=0; k1=m; max_b=0; int max_a=dp(n,0,k2); cout << max_a << " " << max_b << endl ; } return 0; } int dp(int a,int opt,int k) {
//cout << a << " " << opt << " " << k << endl ; //getchar() ;
int r1,r2; r1=opt; if(r1==0) r2=1; else r2=0; if(a<=0) return 0; if(a<k && a<k1 ) return k1; if(a<k && a>k1) return a ; if(a==k) return a; if(k==0) return 0; if(call[a][k]==1) return save[a][k];
call[a][k]=1; save[a][k]=max(dp(a,r1,k-1) , k+ dp(a-k - dp(a-k,r2,k2),r1,k2) ) ; if(opt==1) max_b=save[a][k];
return save[a][k]; }
int max(int m1,int m2) { if(m1>=m2) return m1; return m2; }
Why do you have as a result is 31, not 32. please make sure that! Read the condition of the problem more carefully: "If there is no money in the budget then applications are not accepted any more." Что для центров важнее: получить больше прибыли или минимизировать прибыль соперника? More money is more important than make less money to opponent. |
|
|