通過數： 1
250：
裸的多重背包，次數是min{budget / cost[i]的下界,tim[i]}，即最多能降多少時間，代價是cost[i]
現場忘了照着版調了一陣。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class FarmvilleDiv2 {
public:
int minTime(vector <int>, vector <int>, int);
};
const int MAXN = + ;
int dp[MAXN];
void zerobag(int w, int v, int budget)
{
for(int i = budget - w; i >= ; i--){
if(dp[i] != -) dp[i + w] = max(dp[w + i], dp[i] + v);
}
}
void totbag(int w, int v, int budget)
{
for(int i = ; i <= budget - w ; i++){
if(dp[i] != -) dp[i + w] = max(dp[i + w], dp[i] + v);
}
}
void multibag(int num, int w, int budget)
{
if(num * w >= budget)
totbag(w, , budget);
else{
int k = ;
while(k < num){
zerobag(k * w, k, budget);
num -= k;
k = k * ;
}
}
}
int FarmvilleDiv2::minTime(vector <int> time, vector <int> cost, int budget) {
int n = time.size();
for(int i = ; i <= budget ; i++) dp[i] = -;
dp[] = ;
int sum = ;
for(int i = ; i < n ; i++){
sum += time[i];
multibag(min(budget / cost[i], time[i]), cost[i], budget);
}
int temp = ;
for(int i = ; i <= budget ; i++) temp = max(temp, dp[i]);
return max(sum - temp, );
}
<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
550：
乍一看以為是博弈，仔細一想就是分類讨論。
因為走出去又可以走回來，是以一旦周圍距離起始點的位置3以内的地方沒有特殊點（比如障礙和出口），就可以判斷出答案了。
直接讨論Alice輸的情況。
情況一：Alice的初始位置周圍都是障礙，動彈不得輸掉
情況二：Alice任意的走出合法一步，這個格子旁邊都有一個出口
情況三：總步數是偶數
但是其實還要注意Alice馬上就赢的情況，這種情況高于前面輸的情況
情況一：Alice的起點旁邊就有出口
情況二：k=1
然而現場漏了k=1的情況……
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class BoardEscapeDiv2 {
public:
string findWinner(vector <string>, int);
};
int dx[] = {-, , , };
int dy[] = {, , , -};
int r, c;
bool valid(int x, int y)
{
if(x < || x >= r) return false;
if(y < || y >= c) return false;
return true;
}
bool check1(int x, int y, vector <string>s)
{
for(int i = ; i < ; i++){
int tx = x + dx[i];
int ty = y + dy[i];
if(valid(tx, ty) && s[tx][ty] != '#'){
if(s[tx][ty] == '.') return true;
}
}
return false;
}
bool check3(int x, int y, vector <string> s)
{
int ok = ;
for(int i = ; i < ; i++){
int tx = x + dx[i], ty = y + dy[i];
if(valid(tx, ty) && s[tx][ty] == 'E'){
return true;
}
}
return false;
}
bool check2(int x, int y, vector <string> s)
{
int ok = ;
for(int i = ; i < ; i++){
int tx = x + dx[i];
int ty = y + dy[i];
if(valid(tx, ty) && s[tx][ty] != '#'){
if(!check3(tx, ty, s)){
return true;
}
}
}
return false;
}
string BoardEscapeDiv2::findWinner(vector <string> s, int k) {
r = s.size(), c = s[].size();
int x, y;
x = y = -;
for(int i = ; i < r ; i++){
for(int j = ; j < c ; j++){
if(s[i][j] == 'T'){
x = i, y = j;
break;
}
}
if(x != -) break;
}
string s1 = "Alice";
string s2 = "Bob";
for(int i = ; i < ; i++){
int tx = x + dx[i], ty = y + dy[i];
if(valid(tx, ty) && s[tx][ty] == 'E'){
return s1;
}
}
if(!check1(x, y, s) && k != ) return s2;
if(!check2(x, y, s)) return s2;
if(k % == ) return s2;
return s1;
}
<%:testing-code%>
//Powered by [KawigiEdit] 2.0!