250pt:
题意：定义一种函数f(x),表示ｘ不断/2直到出现非素数的操作次数。现在给定N，D。求X<= N, 并且f(x) >= D的最大的数
思路：直接先弄一个1000w以内的质数表，然后直接dp。由于题目给定内存才64M。。所以没法开1000w的int数组
所以dp时我直接对每个素数做。dp[i]表示以第i个质数结尾的f值。。
code：
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std; #define PB push_back
#define MP make_pair #define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII;
bool vis[];
vector<int> P;
int dp[];
class PrimeSequences
{
public:
void getPrime(int n){
P.clear();
for (int i = ; i <= n; ++i){
if (vis[i]) continue;
P.push_back(i);
for (int j = i * ; j <= n; j += i)
vis[j] = true;
} }
int getLargestGenerator(int N, int D)
{
getPrime(N);
int n = P.size();
int p, x;
int ans = ;
for (int i = ; i < n; ++i){
x = (P[i] >> );
p = lower_bound(P.begin(), P.end(), x) - P.begin();
if (x == P[p]) dp[i] = dp[p] + ;
else dp[i] = ;
ans = max(dp[i], ans);
}
if (ans < D) return -;
for (int i = n-; i >= ; --i)
if (dp[i] >= D) return P[i];
return -;
} };
500pt：
题意：题目给了最多n(n <= 25)个点的有向图，编号0~n-1, 现在求一条0号点到n-1点的最短路，并且该最短路上任意两点距离不为13倍数。
思路：很明显的动态规划。
后面改成3维dp[i][j][k]，表示到达点i，从起点到点i所有路径%13的集合为j，并且此时最短路%13为k时的最短路。
那么转移就很明显了。。
不过此题很容易想入非非了，刚开始就是用2维写错了。少枚举了第三维。直接用最短路%13作为第三维。。
这样的结果就可能导致当前最优而后面不一定最优。。
code：
#line 7 "ThirteenHard.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std; #define PB push_back
#define MP make_pair
#define Inf 0xfffffff
#define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)
#define two(i) (1 << i)
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII;
struct oo{
int x, y, z;
oo(){}
oo(int _x, int _y, int _z):x(_x), y(_y), z(_z){}
};
int dp[][ << ][];
bool vis[][ << ][];
class ThirteenHard
{
public:
int g[][], n;
int calcTime(vector <string> s)
{
n = s.size();
for (int i = ; i < n; ++i)
for (int j = ; j < n; ++j){
if (s[i][j] == '#') g[i][j] = Inf;
if (s[i][j] >= 'A' && s[i][j] <= 'Z') g[i][j] = s[i][j] - 'A' + ;
if (s[i][j] >= 'a' && s[i][j] <= 'z') g[i][j] = s[i][j] - 'a' + ;
}
memset(dp, -, sizeof(dp));
memset(vis, , sizeof(vis));
dp[][][] = ;
queue<oo> q;
q.push(oo(,,));
int x, y, z;
vis[][][] = true;
oo cur;
while (!q.empty()){
cur = q.front();
for (int i = ; i < n; ++i) if (g[cur.x][i] < Inf){
z = (cur.z + g[cur.x][i]) % ;
if (two(z) & cur.y) continue;
y = (cur.y | two(z));
x = i;
if (dp[x][y][z] == - || dp[x][y][z] > dp[cur.x][cur.y][cur.z] + g[cur.x][x]){
dp[x][y][z] = dp[cur.x][cur.y][cur.z] + g[cur.x][x];
if (!vis[x][y][x]){
vis[x][y][z] = true;
q.push(oo(x, y, z));
}
}
}
q.pop();
vis[cur.x][cur.y][cur.z] = false;
}
int ans = -;
for (int i = ; i < two(); ++i)
for (int j = ; j < ; ++j)
if (dp[n-][i][j] > -)
if (ans == - || dp[n-][i][j] < ans) ans = dp[n-][i][j];
return ans;
} };