USACO - 3.1.6 - Stamps

本文主要是介绍USACO - 3.1.6 - Stamps，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://qingtangpaomian.iteye.com/blog/1635988

 

package session_3_1_6;import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;public class stamps {public static void main(String[] args) throws Exception {
//		Scanner in = new Scanner(System.in);
//		PrintWriter pw = new PrintWriter(System.out);Scanner in = new Scanner(new BufferedReader(new FileReader("stamps.in")));PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("stamps.out")));int K = in.nextInt();int N = in.nextInt();int[] needs = new int[2000000]; //动态规划用数组 ， needs[i]表示产生面值为i的邮资所用的最少的邮票数量。int[] stamps = new int[N]; //输入提供的各种邮票的面值Arrays.fill(needs, Integer.MAX_VALUE);for (int j=0;j<N;j++){stamps[j] = in.nextInt();}int i = 0;needs[0] = 0;for (;needs[i]<=K;){i++;for (int j=0;j<stamps.length;j++){if (stamps[j]<=i){needs[i] = min(needs[i] ,needs[i-stamps[j]]+1); //状态转移方程}}}pw.println(i-1);pw.close();}public static int min(int a , int b){return a<b?a:b;}}

下面是上面题的升级版

http://sfiction.blog.163.com/blog/static/1994040102012520113738298/

给定一个信封，最多只允许粘贴N张邮票，计算在给定K种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大max，使得1-max之间的每一个邮资值都能得到。
　 　例如，N=3，K＝2，如果面值分别为1分、4分，则在l分-6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3 分，则在1分-7分之间的每一个邮资值都能得到。可以验证当N=3，K＝2时，7分就是可以得到连续的邮资最大值，所以max=7，面值分别为l分、3 分。
[数据范围]
100%的数据，N + K <= 14

这道题真是混蛋……开始是动态规划没写全WA了两次，修正以后无数2B错误连WA三次，唯一的欣慰就是最优解排在第七。
DFS+DP。DFS枚举所有可能的构造方式，用背包解决0..M的面值用当前邮票凑出的最小代价。

/*
ID: Sfiction
OJ: RQNOJ
PROB: 112
*/
#include <stdio.h>
#define M 500
int a[20],f[M],ans[20];
int N,K,MAX,g=1<<29;
void DFS(int k,int s)
{int i,j,t[M];if (k==K){if (s>=MAX)for (MAX=s,i=1;i<=K;i++) ans[i]=a[i];return;}for (i=0;i<M;i++) t[i]=f[i];for (i=a[k]+1;i<=s;i++){for (j=0;j<M-i;j++)if (f[j]+1<f[j+i]) f[j+i]=f[j]+1;for (j=s;f[j]<=N;j++);a[k+1]=i;DFS(k+1,j);for (j=0;j<M;j++) f[j]=t[j];}
}
int main()
{int i;scanf("%d%d",&N,&K);a[1]=1;for (i=1;i<=N;i++) f[i]=i;for (;i<M;i++) f[i]=g;DFS(1,N+1);for (i=1;i<=K;i++) printf("%d ",ans[i]);printf("\nMAX=%d",MAX-1);return 0;
}

这篇关于USACO - 3.1.6 - Stamps的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---