首页 > 其他分享 >P1474 [USACO2.3] Money System / [USACO07OCT]Cow Cash G

P1474 [USACO2.3] Money System / [USACO07OCT]Cow Cash G

时间:2024-05-26 15:23:07浏览次数:26  
标签:USACO07OCT Cow P1474 int ll long tie include dp

有点水,但是细究还是有点意思的题目
https://www.luogu.com.cn/problem/P1474

一开始的代码:

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;
const int N = 30;
int w[N];
int dp[10010];
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int v, n; cin >> v >> n;
	for (int i = 1; i <= v; i++)cin >> w[i];
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int k = 1; k <= v; k++)
		{
			if (i >= w[k])dp[i] += dp[i - w[k]];
		}
	}
	cout << dp[n];
	return 0;
}

但是运行下来发现样例是128,没办法过,仔细分析了一下,发现这样的方法是把1 2 11 1 2都计数了,但是这样实际上是不行的,如果顺序有影响也应该是“走电梯”的题目(一步走1/2/3格楼梯,走到x楼梯需要几步),所以:

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;
const int N = 30;
ll w[N];
ll dp[10010];
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	ll v, n; cin >> v >> n;
	for (int i = 1; i <= v; i++)cin >> w[i];
	dp[0] = 1;
	for (int k = 1; k <= v; k++)//注意这里!!!!!!
	{
		for (int i = w[k]; i <= n; i++)//注意这里!!!!!!!!!!
		{
			dp[i] += dp[i - w[k]];
		}
	}
	cout << dp[n];
	return 0;
}

顺序无关,那么就采用铺硬币的方式,按硬币的面值一点一点铺过去,这样就不会重复
以及,开longlong,/(ㄒoㄒ)/~~,白交两次

标签:USACO07OCT,Cow,P1474,int,ll,long,tie,include,dp
From: https://www.cnblogs.com/zzzsacmblog/p/18213722

相关文章

  • 【题解】 [USACO 2009 Mar] Cow Frisbee Team S
    题目描述题意分析从\(N\)个整数中取若干个(不能不选),且取的数之和为\(F\)的倍数的总方案数对\(10^8\)取余的值。思路这道题是一道二维线性DP。那么根据线性DP的解题方法。首先,找出题目的阶段性。这道题显而易见方案数随着选择的个数而变化,那么这道题就以选择的个数作为阶段......
  • P3611 [USACO17JAN] Cow Dance Show S
    原题链接题解一句话总结:第\(i\)头奶牛继承场上\(k\)头奶牛里结束时间最短的code#include<bits/stdc++.h>usingnamespacestd;intn,t;intd[100005];intcheck(intk){priority_queue<int,vector<int>,greater<int>>q;for(inti=1;i<=n;i++)......
  • P3007 [USACO11JAN] The Continental Cowngress G
    P3007[USACO11JAN]TheContinentalCowngressG题目链接思路:2-SAT模板,经典的或条件,那么直接建图即可,对于可行解,我们直接枚举每个方案支持和反对,然后染色判断即可。代码:#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_......
  • The cowherd and the weaving maid
    ThecowherdandtheweavingmaidInthecelestialcourtoftheJadeEmperorlivedsevenprincesses.Eachhadtheirchosenplaceincourt,buttheyoungestprincesshadaspecialskill.Shecouldpluckcloudsfromtheskyandspinthemintothesoftestrob......
  • 挑战程序设计竞赛 2.2章习题 POJ - 3617 Best Cow Line 贪心
    FJ正准备带着他的N头奶牛(1≤N≤2,000)参加一年一度的“年度最佳农民”比赛。在这个比赛中,每个农民都会将他的奶牛排成一行,然后引导它们经过评委。今年比赛的组织者采用了一种新的注册方案:只需按照它们出现的顺序注册每头奶牛的首字母(即如果FJ带着Bessie、Sylvia和Dora依次出......
  • P4183 [USACO18JAN] Cow at Large P
    题目首先有结论:一个点为关键点(可以由该点的子树中出发,正好在该点拦截住奶牛),当且仅当\(g_u\ledist(root,u),g_{fa}>dist(root,fa)\),其中\(g_u\)表示距离\(u\)最近的叶节点。那么\(18pts\)就是\(O(n^2)\)的暴力了voiddfs(intu,intfa){ dis[u]=(G.d[u]==......
  • 使用qemu-system-x86_64和cloud-init修改qcow2镜像密码
    方法来自于:CoretutorialwithQEMU依次执行下面的命令sudoaptinstallqemu-system-x86mkdirtempcdtemp#以此镜像为例wgethttps://cloud-images.ubuntu.com/jammy/current/jammy-server-cloudimg-amd64.imgcat<<EOF>user-data#cloud-configpassword:123ch......
  • P2340 [USACO03FALL] Cow Exhibition G
    原题链接题解1.考虑到每个牛只有选或不选两种选择,这样暴力搜索的思路便产生了2.还是上面的思路,怎么优化呢?想想背包数组,其下标是什么?是体积其值是是什么?是价值是在体积相同的情况下选择价值最高的,本题也是,最优解一定是相同智商里情商最高的3.价值和体积都是负数,怎么解决?cod......
  • P2853 [USACO06DEC] Cow Picnic S
    简单的一道深搜:思路:让每个有奶牛的农场沿着道路跑下去,跑到的农场加上root地方的奶牛数量,最后统计能有k头奶牛的农场数量就是答案代码:#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<string.h>#inclu......
  • The cowherd and the weaving maid
    ThecowherdandtheweavingmaidInthecelestialcourtoftheJadeEmperorlivedsevenprincesses.Eachhadtheirchosenplaceincourt,buttheyoungestprincesshadaspecialskill.Shecouldpluckcloudsfromtheskyandspinthemintothesoftestrob......