描述
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;}新闻热点
疑难解答
