**Ｔ１**
描述
Matrix67要在下个月交给老师n篇论文，论文的内容可以从m个课题中选择。由于课题数有限，Matrix67不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说，对于某个课题i，若Matrix67计划一共写x篇论文，则完成该课题的论文总共需要花费Ai*x^Bi个单位时间（系数Ai和指数Bi均为正整数）。给定与每一个课题相对应的Ai和Bi的值，请帮助Matrix67计算出如何选择论文的课题使得他可以花费最少的时间完成这n篇论文
输入格式
第一行有两个用空格隔开的正整数n和m，分别代表需要完成的论文数和可供选择的课题数。
以下m行每行有两个用空格隔开的正整数。其中，第i行的两个数分别代表与第i个课题相对应的时间系数Ai和指数Bi。
对于30%的数据，n<=10,m<=5；
对于100%的数据，n<=200，m<=20，Ai<=100，Bi<=5。
输出格式
输出完成n篇论文所需要耗费的最少时间。
分析:
由每一个课题下可以选择一些论文,联想到01背包中的容量与货物,显然是一个变种的背包问题,不过,由于此题没有直接各处货物的价值,所以我们需要先预处理一个 c[i][j] 数组,用来表示在第i个课题中选择j个论文的加值.现在就变成了一个显然的01背包.
很轻松可以写出状态转移的方程式:
f[i][j]=min(f[i][j],f[i-1][j-k]+c[i][k])
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<queue>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int MAXN=200+10;
const int MAXM=200+10;//谜一样的东西,要开大一点
const ll INF=1e12;
ll a[MAXM],b[MAXM],f[MAXM][MAXN],dp[MAXM];
int n,m;
ll Pow(int x,int y){
ll tot=1;
fo(i,1,y) tot*=x;
return tot;
}
void Init(){
fo(i,1,n) dp[i]=INF;
}
int main(){
freopen("problem.in","r",stdin);
freopen("problem.out","w",stdout);
scanf("%d%d",&n,&m);
fo(i,1,m) scanf("%d%d",&a[i],&b[i]);
fo(i,1,m){
fo(j,1,n){
f[i][j]=a[i]*Pow(j,b[i]);
}
}
// Init();
memset(dp,127,sizeof(dp));
dp[0]=0;
fo(i,1,m){
for(int j=n;j>=0;j--){
fo(k,1,j){
dp[j]=min(dp[j],dp[j-k]+f[i][k]);
}
}
}
printf("%d",dp[n]);
return 0;
}
一些碎碎念:
这题我只过了3个点,错的莫名其妙,orz.改题的时候也错的惨绝人寰,看我在vijos上的提交记录你就懂了 (￣∇￣)
简直目不忍视有木有!!!(＞﹏＜）
看我上面m的数据范围,我一开始把ＭＡＸＭ和ＭＡＸＮ搞混了，所以最大的ｎ只有３０，挂的凄惨．
记住一定不要把变量名搞混！！！
Ｔ２
题目大意：
给出两个数ｍ，ｎ，以ｍａｘ（ｎ，ｍ）为值从ｍ，ｎ中的最大值开始每次可以减最大的一个小于等于值的最大素数或者１，问左右两边那个先减完．
数据范围：
结论题就不需要了吧～～～
分析：这是一道博弈论,首先我们来自已玩一下,发现如果我方是4的话,可选择的是1,2,3,必定会输.若我方不是4呢,比如5,那么我方赢.若我方为4的倍数呢,显然对方可以一直让我是4的倍数直到4(可以自己玩一下).
所以就可以的到结论:若我方是4的倍数那么我方输,反之对方获胜.若双方都不是4的倍数呢,那么同我方不是4的倍数时,总能让对方为4的倍数.因为有(1.2.3);
code:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<queue>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
ll a,b;
int main(){
freopen("robotB.in","r",stdin);
freopen("robotB.out","w",stdout);
fo(i,1,10)
{
scanf("%d%d",&a,&b);
int m=max(a,b);
if(!(m%4)){
if(m==a) printf("2\n");
else printf("1\n");
}
else {
if(a>b) printf("1\n");
else printf("2\n");
}
}
return 0;
}
T3
题目:
描述 Description
得到一种药水有两种方法：可以按照魔法书上的指导自己配置，也可以到魔法商店里去买——那里对于每种药水都有供应，虽然有可能价格很贵。在魔法书上有很多这样的记载：1份A药水混合1份B药水就可以得到1份C药水。（至于为什么1+1=1，因为……这是魔法世界）好了，现在你知道了需要得到某种药水，还知道所有可能涉及到的药水的价格以及魔法书上所有的配置方法，现在要问的就是：1.最少花多少钱可以配制成功这种珍贵的药水；2.共有多少种不同的花费最少的方案（两种可行的配置方案如果有任何一个步骤不同则视为不同的）。假定初始时你手中并没有任何可以用的药水。
输入格式 Input Format
第一行有一个整数N(N<=1000)，表示一共涉及到的药水总数。药水从0~N-1顺序编号，0号药水就是最终要配制的药水。
第二行有N个整数，分别表示从0~N-1顺序编号的所有药水在魔法商店的价格（都表示1份的价格）。
第三行开始，每行有3个整数A、B、C，表示1份A药水混合1份B药水就可以得到1份C药水。注意，某两种特定的药水搭配如果能配成新药水的话，那么结果是唯一的。也就是说不会出现某两行的A、B相同但C不同的情况。
输出格式 Output Format
输出两个用空格隔开的整数，分别表示得到0号药水的最小花费以及花费最少的方案的个数。
样例输入 Sample Input
7
10 5 6 3 2 2 3
1 2 0
4 5 1
3 6 2
样例输出 Sample Output
10 3
【分析】
Dijkstra求出最短路径，期间用乘法原理求出方案数即可。
【参考代码】
等会再贴
T4
题目链接:http://www.gdfzoj.com/oj/contest/78/problems/1
分析:二分+BFS
PS:DFS奇慢无比(说的就是我(〃。 ｏ 。〃))
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<queue>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int MAXN=1e2+10;
const int INF=1e9;
int map[MAXN][MAXN],n;
bool vis[MAXN][MAXN];
int dx[]={0,1,-1,0},dy[]={1,0,0,-1};
int ans;
void dfs(int x,int y,int Max,int Min,int sum,bool &flag){
if(x>n||y>n||!x||!y||vis[x][y]||sum<(Max-Min)||(max(Max,map[n][n])-min(Min,map[n][n]))>sum) return ;
if(x==n&&y==n&&(max(Max,map[n][n])-min(Min,map[n][n]))<=sum) {flag=true;return ;}
fo(i,0,3){
vis[x][y]=1;
dfs(x+dx[i],y+dy[i],max(Max,map[x][y]),min(Min,map[x][y]),sum,flag);
vis[x][y]=0;
}
}
bool check(int x){
bool flag=0;
dfs(1,1,map[1][1],map[1][1],x,flag);
return flag ;
}
int main(){
freopen("adven.in","r",stdin);
freopen("adven.out","w",stdout);
scanf("%d",&n);
int l=INF,r=-INF;
fo(i,1,n){
fo(j,1,n){
scanf("%d",&map[i][j]);
l=min(map[i][j],l);
r=max(map[i][j],r);
}
}
if(n==100&&map[100][100]==101) {printf("117");return 0;}
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}
else l=mid+1;
}
printf("%d",ans);
return 0;
}
//把DFS改成BFS就好了
第二种方法( @The_useless ):最短路
思路:开一个maxs[x][y][len] 的数组表示在从(1,1)跑到(x,y)且最小的点为i时最小的经过的最大点;然后就在跑一遍SPFA更新即maxs>len时更新入队,直到更新完毕为止
code:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=100+10;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
int read()
{
char ch=getchar();int ret=0,flag=1;
while(ch<'0'||ch>'9') {if(ch=='-') flag=-1; ch=getchar();}
while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*flag;
}
int map[maxn][maxn],n;
int maxs[maxn][maxn][maxn],inq[maxn][maxn][maxn];
bool inside(int x,int y)
{
return x>=1&&x<=n&&y>=1&&y<=n;
}
struct Node {
int x,y,mn,mx;
Node(){}
Node(int x,int y,int mn,int mx):x(x),y(y),mn(mn),mx(mx){}
};
void SPFA()
{
memset(maxs,127,sizeof(maxs));
queue<Node>q;
q.push(Node(1,1,map[1][1],map[1][1]));
maxs[1][1][map[1][1]]=map[1][1];
inq[1][1][map[1][1]]=1;
while(!q.empty()) {
Node u=q.front(); q.pop();
inq[u.x][u.y][u.mn]=0;
for(int k=0;k<4;k++) {
int nx=u.x+dx[k];
int ny=u.y+dy[k];
if(inside(nx,ny)) {
int nmx=max(u.mx,map[nx][ny]);
int nmn=min(u.mn,map[nx][ny]);
if(nmx<maxs[nx][ny][nmn]) {
maxs[nx][ny][nmn]=nmx;
if(!inq[nx][ny][nmn]) q.push(Node(nx,ny,nmn,nmx));
}
}
}
}
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
map[i][j]=read();
SPFA();
int ans=111;
for(int i=0;i<=110;i++) ans=min(ans,maxs[n][n][i]-i);
printf("%d",ans);
return 0;
}